# cython: language_level=3
# cython: profile=True
"""Fiber

A class used to implement the fibers (or the entire **fibertree**) of
a tensor.

"""

import logging
from sys import exit

import bisect
import copy
import sys
from functools import partialmethod
from itertools import product

import numbers
import pickle
import random

import yaml

from .any import Any
from .coord_payload import CoordPayload
from .iterators import coiterShape, coiterShapeRef, coiterActiveShape, \
    coiterActiveShapeRef, coiterRangeShape, coiterRangeShapeRef, intersection, \
    union
from .metrics import Metrics
from .payload import Payload
from .rank_attrs import RankAttrs

#
# Set up logging
#
module_logger = logging.getLogger('fibertree.core.fiber')


#
# Define an error class
#
class CoordinateError(Exception):
    """CoordinateError"""
    pass


class PayloadError(Exception):
    """PayloadError"""
    pass


#
# Define the fiber class
#
class Fiber:
    """A base class for representing a tensor as a tree of fibers

    The Fiber class implements the concept of a fiber of a tensor.  A
    Fiber is comprised of a list of **coordinates** and associated
    **payloads**.

    Fiber coordinates are unique tags for each element of the Fiber,
    they are often integers in the open range [0 to **shape**), where
    **shape** is an attribute of the Fiber.  However, coordinates may
    be other types, such as `tuples`. For example, `tuple` coordinates
    can be generated by `Fiber.flattenRanks()`.

    Fiber payloads are a value associated with each
    coordinate. Payloads may themselves be Fibers, which permits the
    creation of **fibertrees**. The payloads of the leaf level of the
    fibertree will be terminal values. Since we want to enable code to
    hold and update a payload (outside the context of the Fiber) we
    usually **box** the leaf level payloads using the `Payload` class
    (see `fibertree.core.payload`).

    A Fiber may have not have values for every possible coordinate
    (i.e., the coordinate list may have gaps). Such missing
    coordinates are referred to as being **empty**.

    Fibers can be iterated and return a series of `CoordPayload`
    elements (see `fibertree.core.coord_payload`).

    Attributes
    ----------

    Fibers have a set of attributes that can be set and
    accessed. These include:

    - A **default** value, which is the value associated with an
      **empty** coordinate and is accessed with `Fiber.getDefault()`
      and may be returned by methods that access a point in the Fiber
      such as `Fiber.getPayload()` and `Fiber.getPayloadRef()`.

    - A **shape**, which specifies the **size** of the fiber and
      controls the range of legal (integer) coordinates. The shape of
      an individual fiber is an integer, while the shape of a
      fibertree will be a list of integers corresponding to the
      shapes of the fibers at each level of the tree. A fiber's (or
      fibertree's) shape can be accessed with `Fiber.getShape()`

    - An **ordered** attribute which indicates and maintains the
      invariant that the coordinates of the fiber are monitonically
      increasing.

    - A **unique** attribute which indicates and maintains the
      invariant that the coordinates of the fiber are unique.

    - An **owner** rank. Since fibers are often part of a `Tensor`,
      the fiber may have an owning rank (see `Fiber.setOwner()`). When
      owned by a rank, some fiber atributes are actually obtained from
      that rank rather than being stored locally.

    - A **savedPos**, which is a value stored by certain methods that
      records a postion in a fiber that can be used in the future as a
      **shortcut** to accelerate a search in the fiber by another
      method. See `Fiber.iterShape()` for an example of a method that
      both saves and can use these **shortcuts**.

    Constructor
    -----------

    The `Fiber` constructor creates an fiber with a given set of
    coordinates and payloads (in struct of lists form).

    Parameters
    ----------

    coords: list, default=[]
        List of coordinate values

    payloads: list, default=[]
        List of corresponding payloads for the coordinates

    default: value, default=0
        Default value of a payload in this fiber

    shape: integer, default=None
        Declared shape for the fiber

    initial: value, default=None
        A value to initialize all payloads.

    max_coord: value, default=no maximum coordinate
            The maximum legal coordinate value (this is really "shape-1")

    ordered: Boolean, default=True
        Attribute specifing that the coordinates are monotonically increasing

    unique: Boolean, default=True
        Attribute specifing that the coordinates are unique


    Notes
    -----

    Elements of the fiber have a `position` that can be used to
    reference the element. Generally one can think of the `position` as
    the relative address of the element in the concrete represention of
    the fiber. A variety of methods use a `postion` to reference an
    element, such as `Fiber.__getitem__()` and `Fiber.__setitem__()`

    Currently, the internal implementation of a Fiber is to hold a list
    of coordinates and a list of payloads (struct of lists) and the
    instance variables holding those lists (coords and payloads) are
    currently left public...

    """


    def __init__(self,
                 coords=None,
                 payloads=None,
                 default=0,
                 shape=None,
                 initial=None,
                 max_coord=None,
                 ordered=True,
                 unique=True,
                 rank_attrs=None,
                 active_range=None):

        #
        # Set up logging
        #
        # self.logger = logging.getLogger('fibertree.core.fiber')

        #
        # Collect attributes
        #
        self._ordered = ordered
        self._unique = unique

        #
        # Handle cases with missing inputs
        #
        if coords is None:
            if payloads is None:
                #
                # If neither coords or payloads are given create an empty fiber
                #
                coords = []
                payloads = []
            else:
                #
                # If only payloads are given create a "dense" fiber
                #
                # TBD: Reconcile coords with shape
                #
                coords = list(range(len(payloads)))
        else:
            if payloads is None:
                #
                # If only coords are given create a set of payloads
                #
                # TBD: Creating a set of zeros is odd...
                #
                payloads = len(coords)*[initial]


        assert (len(coords) == len(payloads)), \
            "Coordinates and payloads must be same length"

        #
        # Note:
        #    If a payload is already boxed, Payload.maybe_box() will
        #    NOT double box it.
        #
        #    We do not eliminate explicit zeros in the payloads
        #    so zeros will be preserved.
        #
        self.coords = [coord for coord in coords]
        """The list of coordinates of the fiber"""

        self.payloads = [Payload.maybe_box(p) for p in payloads]
        """The list of payloads of the fiber"""

        #
        # Check that fiber attributes are satisfied
        #
        self._checkOrdered()
        self._checkUnique()

        #
        # Owner rank... set later when fiber is appended to a rank
        #
        self.setOwner(None)

        # Create a rank_attrs
        if rank_attrs is not None:
            self.setRankAttrs(rank_attrs)
        else:
            self.setRankAttrs(RankAttrs())

        #
        # Set a specific contstant value for the shape of this fiber
        #
        # Note1: this value is overridden by the owning rank's shape
        # Note2: no checks are done to see if this value is violated
        #
        if shape is not None:
            self.getRankAttrs().setShape(shape)

        #
        # Set a specific constant value to the maximum legal coordinate
        #
        # TBD: If not None there are lots of places this should be checked
        #
        self._max_coord = max_coord
        if max_coord is not None:
            Fiber._deprecated("Explicitly setting a fiber's max_coord is deprecated")

        #
        # Set the active range
        #
        self.setActive(active_range)

        #
        # Create default value
        #
        self.getRankAttrs().setDefault(Payload.maybe_box(default))

        #
        # Initialize "saved position"
        #
        self._saved_pos = 0

        #
        # Clear all stats
        #
        self.clearStats()

        #
        # By default, Fibers are eager
        #
        self._setIsLazy(False)
        self.iter = None

    @classmethod
    def fromCoordPayloadList(cls, cp, **kwargs):
        """Construct a Fiber from a coordinate/payload list.

        The base Fiber contructor creates a fiber from a list of a
        coordinates and a list of payloads (i.e., struct of lists
        form) this constructor takes a list of coordinate/payload
        tuples (i.e., list of structs form).

        Parameters
        ----------

        cp: list of tuples
            A sequence of fiber elements as (coord, payload) tuples

        kwargs: keyword arguments
            Keyword arguments accepted by `Fiber.__init__()`

        Todo
        ----

        Support a list of `CoordPayload` elements

        """

        (coords, payloads) = zip(*cp)

        return cls(coords, payloads, **kwargs)


    @classmethod
    def fromYAMLfile(cls, yamlfile, default=0, **kwargs):
        """Construct a Fiber from a YAML file

        Parameters
        ----------

        yamlfile: str
            The name of a YAML file holding a description of a fiber

        kwargs: keyword arguments
            Keyword arguments accepted by `Fiber.__init__()`

        """

        (coords, payloads) = Fiber.parse(yamlfile, default)

        return cls(coords, payloads, default=default, **kwargs)


    @classmethod
    def fromUncompressed(cls, payload_list, default=0):
        """Construct a Fiber from an uncompressed nest of lists.

        The coordinates of the Fiber will be infered from the postions
        of the values in the lists. Zeros in the lists will be
        interpreted as the empty value of the Fiber.


        Parameters
        ----------

        payload_list: list
            A nest of lists holding the values of the Fiber.

        kwargs: keyword arguments
            Keyword arguments accepted by `Fiber.__init__()`


        Notes
        -----

        Zero values and sub-fibers that are all zeros are squeezed
        out, i.e., they will have no coordinates.  Unless the entire
        input is zeros.

        """

        f = Fiber._makeFiber(payload_list, default=default)

        #
        # Check if the list was all defaults, so return an empty fiber
        #
        if f is None:
            # Return something for an entirely empty input
            return Fiber([], [], shape=len(payload_list), default=default)

        return f


    @staticmethod
    def _makeFiber(payload_list, default=0):
        """Recursively make a fiber out of an uncompressed nest of lists"""

        assert(isinstance(payload_list, list))

        if isinstance(payload_list[0], list):
            size_check = len(payload_list[0])

            for p in payload_list:
                assert size_check == len(p), \
                       "All lists must be the same length"

        # Create zipped list of (non-empty) coordinates/payloads
        zipped = [(c, p) for c, p in enumerate(payload_list) if p != default]

        #
        # Recursively unzip the lists into a Fiber
        #
        if len(zipped) == 0:
            # Got an empty subtree
            return None

        if isinstance(payload_list[0], list):
            coords = []
            payloads = []

            for c, p in zipped:
                real_p = Fiber._makeFiber(p, default=default)
                if real_p is not None:
                    coords.append(c)
                    payloads.append(real_p)
        else:
            coords = [c for c, _ in zipped]
            payloads = [p for _, p in zipped]

        if len(coords) == 0:
            return None

        #
        # Create fiber
        #
        # Note: max_coord dervived from input argument list and
        #       assuming coordinates start at 0
        #
        return Fiber(coords, payloads, shape=len(payload_list), default=default)


    @classmethod
    def fromRandom(cls, shape, density, interval=10, seed=None, default=0):
        """Create a fiber populated with random values.

        Multi-level fibers are supported by recursively creating
        fibers.

        Parameters
        -----------

        shape: list
            The `shape` (i.e., size) of the fibers at each level of
            the tree.

        density: list or scalar
            The probability that an element of the fiber will not be
            empty for each level of the tree. A scalar is density for
            leaf level of tree and other levels have density 1.0.

        interval: number
            The range (from 0 to `interval`) of each value at the leaf
            level of the tree.

        default: int or None, default=0
            The default empty value

        seed: a valid argument for `random.seed`
            A seed to pass to `random.seed`.


        Notes
        =====

        This method only creates tensors filled with integers.

        The density always is referring to the density of zeros
        irrespective of the `default` empty value for the tensor. Note
        further, that if the `default` is not 0 then setting a non-unit
        density for upper ranks does not make sense.

        """

        if not isinstance(density, list):
            #
            # Convert scalar density to per rank density list
            #
            density = (len(shape)-1)*[1.0] + [density]


        assert len(shape) == len(density), \
               "Density and shape arrays must be same length"

        assert len(density) == 1 or density[0] == 1.0 or default is not None, \
            "Non-unit density for higher ranks illegal when default is None"

        if seed is not None:
            random.seed(seed)

        coords = []
        payloads = []

        for c in range(shape[0]):
            if random.random() < density[0]:
                if len(shape) == 1:
                    payload = random.randint(1, interval)
                    if payload == default:
                        continue
                else:
                    payload = Fiber.fromRandom(shape[1:],
                                               density[1:],
                                               interval,
                                               default=default)
                    if payload.isEmpty():
                        continue
            else:
                if default == 0:
                    continue

                payload = 0

            coords.append(c)
            payloads.append(payload)

        f = Fiber(coords, payloads, default=default)

        return f

    @classmethod
    def fromIterator(cls, iter_,  **kwargs):
        """
        Create a lazy fiber using an iterator (elements are only filled when
        accessed)

        Parameters
        -----------

        iter_: Iterator
            Iterator that returns the elements of the fiber as CoordPayloads

        """
        f = cls(**kwargs)

        f.iter = iter_
        f._setIsLazy(True)

        return f

    @classmethod
    def fromLazy(cls, fiber, **kwargs):
        """
        Create an eager fiber from a lazy fiber

        WARNING: does not correctly maintain links for lazy fibers created
        with the populate (<<) operator

        Parameters
        ----------

        fiber: Fiber
            The lazy fiber to build from
        """

        f_out = cls(**kwargs, default=fiber.getDefault())

        for c, (f_ref, f_val) in f_out << fiber:
            f_ref <<= f_val

        return f_out


#
# Stats-related methods
#

    def clearStats(self):
        """Clear savedPos-related statistics

        See `Fiber.getSavedPos()` for more information.
        NDN: Make sure this is actually the method that should be used
        for clearing metrics

        """

        self._clearSavedPosStats()


#
# Accessor methods
#
    def getCoords(self):
        """Return the list of coordinates in fiber

        Returns
        -------
        coord_list: list
            List of coordinates

        Notes
        -----

        This method should be used in preference to accessing the
        `Fiber.coords` class instance variable directly.

        """
        assert not self.isLazy()

        return self.coords

    #
    # The following two methods are workarounds for traversing
    # a fiber with "tuple" coordinates for the uncompressed display
    #
    def iterUncompressed(self):
        """ Temporary function """

        index = 0
        max_index = len(self.coords) - 1


        shape = self.getShape(all_ranks=False)
        assert max_index == -1 or isinstance(self.coords[0], type(shape)), \
            "The type of coordinates must match type of shape"

        for c in self.iterShapeCoords():
            if index <= max_index and c == self.coords[index]:
                yield CoordPayload(c, self.payloads[index])
                index += 1
            else:
                p = self._createDefault(addtorank=False)
                yield CoordPayload(c, p)

    def iterShapeCoords(self, start=None, end=None, shape=None):
        """ Temporary function """

        def recursive_product(sublist):
            if isinstance(sublist, list) or isinstance(sublist, tuple):
                ranges = [recursive_product(item) for item in sublist]
                return [items for items in product(*ranges)]
            else:
                return range(sublist)

        if shape is None:
            shape = self.getShape(all_ranks=False)

        #
        # Handle case where shape is just an integer
        # by converting it into a list
        #
        if isinstance(shape, int):
            shape = [shape]

        #
        # Handle single-dimension shapes with integer coordinates
        #
        if len(shape) == 1 and isinstance(shape[0], int):

            if start is None:
                start = 0

            if end is None:
                end = shape[0]

            for item in range(start, end, 1):
                yield item
            return

        #
        # Handle other cases
        #
        if len(shape) == 1:
            #
            # Handle single-dimension shape with non-integer coordinates
            #
            iterator = self.iterShapeCoords(shape=shape[0])
        else:
            #
            # Handle multi-dimension shapes
            #
            ranges = [recursive_product(num) for num in shape]
            iterator = product(*ranges)


        started = start is None

        for item in iterator:
            if not started and item == start:
                started = True

            if started:
                yield item

                if item == end:
                    return



    def getPayloads(self):
        """Return the list of payloads in fiber

        Returns
        -------
        payload_list: list
            List of payloads

        Notes
        -----

        This method should be used in preference to accessing the
        `Fiber.payloads` class instance variable directly.

        """
        assert not self.isLazy()

        return self.payloads


    def isOrdered(self):
        """Return the status of the "ordered" attribute

        Returns
        -------
        is_ordered: Boolean
            Set to True if the coordinates are ordered


        Note: this attribute cannot be changed after fiber creation.

        """
        return self._ordered


    def isUnique(self):
        """Return the status of the "unique" attribute

        Returns
        -------
        is_unique: Boolean
            Set to True if the coordinates are ordered

        Note: this attribute cannot be changed after fiber creation.

        """

        return self._unique


#
# Coordinate-based methods
#
# The following set of methods all reference an element in the fiber
# by coordinate. Some just obtain information about the element (non-mutating)
# others change the content of the fiber (mutating)
#

    def getPayload(self, *coords, default=None, allocate=True, start_pos=None, trace=None):
        """Get the payload at a **point** in a fibertree

        Return the final payload after recursively traversing the
        levels of the fiber tree for at each coordinate in coords. If
        the list of coordinates reaches a leaf of the tree, it returns
        a value otherwise it will return a fiber. [Non-mutating]

        This method operates in two modes: allocate=True and False.

        For "allocate=True" mode, if any coordinate refers to a
        non-existent element, a payload is created (a fiber for at a
        non-leaf level or a zero at the leaf) recursively, but not
        inserted into the fiber tree. The final such payload is
        returned to the caller.

        For "allocate=False" mode, if any coordinate refers to a
        non-existent element, nothing is created and the `default`
        value is returned.

        If `start_pos` is specified it is used as a shortcut to start the
        search for the coordinate. And a new position is saved for use in
        a later search. Only works for a one-deep search.

        Parameters
        ----------

        coords: list
            list of coordinates to traverse

        allocate: Boolean, default=True
            Automatically generate the default value if needed at each
            level of the tree, but don't insert into the tree.

        default: value, default=None
            A constant default value to return if coordinate is empty on
            no-allocate

        start_pos: scalar or Payload() containing a scalar, default=None
            An optional shortcut value to optimize search

        trace: str
            The name of the metrics traces the accesses should track

        Returns
        -------

        payload: a scalar or Fiber
             The payload of the element at the specified coordinate(s)

        Raises
        ------

        None

        """

        assert not self.isLazy()
        assert default is None or not allocate
        assert start_pos is None or len(coords) == 1

        start_pos = Payload.get(start_pos)
        assert not start_pos or self.coords[start_pos] <= coords[0]

        coord0 = coords[0]

        do_search = True
        const_used = False

        # If the coord is empty skip the search
        if isinstance(coord0, list) and len(coord0) == 1:
            coord0_point = coord0[0]
            if isinstance(coord0_point, tuple) and len(coord0_point) == 0:
                do_search = False
                existing = False
                index = start_pos


        if do_search:
            index = self._coord2pos(coord0, start_pos=start_pos)
            existing = self._coordExists(coord0, index)

        if existing:
            payload = self.payloads[index]
        elif allocate:
            payload = self._createDefault(addtorank=False)
            const_used = not isinstance(payload, Fiber)
        else:
            payload = Payload.maybe_box(default)
            const_used = True

        if Metrics.isCollecting() and trace is not None:
            Metrics.addUse(self.getRankAttrs().getId(), coords[0], index, type_=trace)

        if not const_used and len(coords) > 1:
            assert Payload.contains(payload, Fiber), \
                "getPayload too many coordinates"

            # Recurse to the next level's fiber
            return payload.getPayload(*coords[1:],
                                      default=default,
                                      allocate=allocate,
                                      trace=trace)

        if start_pos is not None:
            if existing or index == 0:
                self.setSavedPos(index, distance=index - start_pos)

            # If the new element is never inserted, the saved pos should be the
            # closest coordinate before that actually exists, but the distance
            # should still be the amount actually traveled
            else:
                self.setSavedPos(index - 1, distance=index - start_pos)

        return payload


    def getPayloadRef(self, *coords, start_pos=None, trace=None):
        """Get a (mutable) reference to a payload in a fibertree

        Return the final payload after recursively traversing the
        levels of the fiber tree for at each coordinate in coords,
        which are essential the coordinates of a `point`.  If the
        payload is empty, then recursively return the `default`
        payload

        If `start_pos` is specified it is used as a shortcut to start the
        search for the coordinate. And a new position is saved for use in
        a later search. Only works for a one-deep search.

        Parameters
        ----------
        coords: coordinates
            List of coordinates to traverse, i.e., a "point"

        start_pos: scalar or Payload() containing a scalar
            Optional shortcut value to optimize search

        Returns
        -------
        payload: a (boxed) scalar or Fiber
           The payload of the element at the specified coordinate(s)

        Raises
        ------

        None

        """

        assert not self.isLazy()
        assert start_pos is None or len(coords) == 1

        # TBD: Actually optimize the search

        start_pos = Payload.get(start_pos)

        # Get the payload for the particular index
        index = self._coord2pos(coords[0], start_pos=start_pos)

        if self._coordExists(coords[0], index):
            payload = self.payloads[index]
        else:
            payload = self._create_payload(coords[0])

        if Metrics.isCollecting():
            Metrics.addUse(self.getRankAttrs().getId(), coords[0], index, type_=trace)

        if len(coords) > 1:
            # Recurse to the next level's fiber
            assert Payload.contains(payload, Fiber), "Too many coordinates"

            return payload.getPayloadRef(*coords[1:], trace=trace)

        if start_pos is not None:
            self.setSavedPos(index, distance=index - start_pos)

        assert Payload.is_payload(payload)

        return payload


    def _create_payload(self, coord, payload=None, pos=None):
        """Create a payload in the fiber at coord

        Optionally insert into the owners rank.

        """

        # Create a payload at coord
        # Temporary value (should be None)

        if payload is None:
            payload = self._createDefault()

        assert Payload.is_payload(payload)

        if pos is None:
            pos = self._coord2pos(coord)

        self.coords.insert(pos, coord)
        self.payloads.insert(pos, payload)

        #
        # Get the payload out of the payloads array
        # TBD: Not sure why I felt this was needed
        #
        payload = self.payloads[pos]

        assert Payload.is_payload(payload)

        return payload

    def _deletePayload(self, coord):
        """Remove a payload """


    def getRange(self,
                 start_coord,
                 size=None,
                 end_coord=None,
                 trans_fn=None,
                 start_pos=None):
        """Extract a range of coordinates from a Fiber

        Return a fiber in the range starting at `start_coord` and ending
        either when the `size` is exceeded or the fiber reaches the end
        of the open interval ending at `end_coord`.

        Parameters
        ----------
        start_coord: coordinate
            A coordinate indicating where to start the new fiber

        size: integer, default=None
            The size of the range in coordinate space

        end_coord: coordinate, default=None
            A coordinate indicating the end of the open interval

        trans_fn: function: coord -> coord, default=None
            A function that converts a coordinate in the orginal fiber
            into a cordinate in the new fiber

        start_pos: scalar or Payload() containing a scalar, default=None
            Optional **shortcut** value to optimize search for `start_coord`

        Returns
        -------

        Fiber
            Fiber containing the requested range


        Notes
        -----

        1) Either `size` or `end_coord` must be specified, but not both.

        2) The resulting fiber will NOT include `end_coord`


        """
        Fiber._deprecated("Fiber.getRange() is deprecated use Fiber.iterRange())")

        assert not self.isLazy()
        assert not (size is None and end_coord is None)
        assert size is not None or end_coord is not None
        assert self._ordered

        if end_coord is None:
            end_coord = start_coord + size

        return self.project(trans_fn=trans_fn, interval=[start_coord, end_coord], start_pos=start_pos)

    def prune(self, trans_fn=None, start_pos=None):
        """Create a new fiber by pruning the elements of an existing fiber

        Return a fiber containing a subset of the coordinates of the
        input fiber. The input fiber is traversed calling `trans_fn`
        for each element. Based on the return value the element is
        included [True] (or not [False]) in the new fiber or
        traversal is stopped [None].

        Note: It is the responsibility of the `trans_fn` to cope with
        the fact that the coordinates of the fiber are "ordered"
        and/or "unique".

        Parameters
        ----------
        trans_fn: function: postion, coord, payload -> {True, False, None}, default=None

            A function that specifies what to do with each element of
            the original fiber.


        start_pos: scalar or Payload() containing a scalar, default=None
            Optional **shortcut** value to optimize search for `start_coord`

        Returns
        -------

        Fiber
            Fiber containing the pruned element of the input Fiber.

        """
        # Check the start_pos
        if start_pos is not None:
            assert not self.isLazy()
            assert start_pos < len(self.coords)

        # Build the iterator
        class prune_iterator:
            fiber = self
            trans = lambda self, i, c, p: trans_fn(i, c, p)
            start = start_pos

            def __iter__(self):
                f_iter = self.fiber.__iter__(tick=False, start_pos=self.start)
                for i, (c, p) in enumerate(f_iter):
                    if self.trans(i, c, p):
                        yield c, p

        result = Fiber.fromIterator(prune_iterator, active_range=self.getActive())
        result._setDefault(self.getDefault())
        result.getRankAttrs().setId(self.getRankAttrs().getId())

        return result



    def getPosition(self, coord, start_pos=None):
        """Find position of element associated with a coordinate [non-mutating]

        Return the position of the elemnt at `coord`, if any. If the
        the element at `coord` is **empty** return None. This method
        is non-mutating, i.e., the fiber will not change as a side
        effect of a call to this method.

        If `start_pos` is specified it is used as a shortcut to start the
        search for the coordinate. And a new position is saved for use in
        a later search. Only works for a one-deep search.

        Parameters
        ----------
        coord: coordinate
            Coordinate to look up

        start_pos: scalar or Payload() containing a scalar, default=None
            Optional shortcut value to optimize search

        Returns
        -------

        position: integer or None
            An index that can be used to _getitem_()

        Raises
        ------

        None

        """

        assert not self.isLazy()

        start_pos = Payload.get(start_pos)

        index = self._coord2pos(coord, start_pos=start_pos)

        if not self._coordExists(coord, index):
            index = None

        if start_pos is not None and index is not None:
            self.setSavedPos(index, distance=index - start_pos)

        return index


    def getPositionRef(self, coord, start_pos=None):
        """Find position of element associated with a coordinate [mutating]

        Return the position of the elemnt at `coord`. If the the
        element at `coord` is **empty** then create it and assign the
        appropriate default payload, e.g., an empty Fiber or a zero.

        If `start_pos` is specified it is used as a shortcut to start the
        search for the coordinate. And a new position is saved for use in
        a later search. Only works for a one-deep search.


        Parameters
        ----------
        coord: coordinate
            Coordinate to look up

        start_pos: scalar or Payload() containing a scalar
            Optional shortcut value to optimize search

        Returns
        -------

        position: integer
            An index that can be used to _getitem_()


        Raises
        ------

        None

        """

        assert not self.isLazy()

        start_pos = Payload.get(start_pos)

        index = self._coord2pos(coord, start_pos=start_pos)

        if not self._coordExists(coord, index):
            self._create_payload(coord)

        if start_pos is not None and index is not None:
            self.setSavedPos(index, distance=index - start_pos)

        return index


    def project(self, trans_fn=None, interval=None, rank_id=None,
                start_pos=None, coord_ex=None, tick=False):
        """Create a new fiber with coordinates projected according to `trans_fn`

        This method creates a new fiber with the same payloads as the
        original fiber, but with the coordinates transformed by `trans_fn`.


        Parameters
        ----------

        trans_fn: function with signature: lambda coord -> coord
            Function to convert a original fiber coordinate into a new
            fiber coordinate.

        interval: tuple, default=None (all coordinates)
            Restict projection to this range of new coordinates

        rank_id: str
            The name of the target rank of the project

        start_pos: int
            Shortcut for the position to start iterating at

        coord_ex: Optional[Union[int, tuple]]
            An example of a coordinate that should appear in the input tensor

        tick: bool
            True if the iteration counter should tick as this iterator moves

        Returns
        -------

        fiber
            Fiber with coordinates projected according to `trans_fn`

        Raises
        ------

        None


        Notes
        -----

        This method returns a fiber that carries forward the "ordered"
        and "unique" attributes of the original fiber.  However, it
        largely does not check that the `trans_fn` maintains those
        attributes. Although it does a crude check to see if the
        coordinates seem to have been reversed.

        """
        if trans_fn is None:
            # Default trans_fn is identify function (inefficient but easy)
            trans_fn = lambda x: x


        # Get an example of a coordinate if one was not provided
        if coord_ex is None:
            if len(self) > 0:
                coord_ex, _ = next(self.iterOccupancy(tick=False))
            else:
                coord_ex = 0

        c0 = Fiber._transCoord(coord_ex, lambda c: 0)
        c1 = Fiber._transCoord(coord_ex, lambda c: 1)

        # Invariant: trans_fn is order preserving, but we check for reversals
        if trans_fn(c0) > trans_fn(c1):
            # Note that we cannot reverse lazy fibers
            assert not self.isLazy()

            # Build an iterator over the reversed fiber
            class reversed_iterator:
                cps = list(zip(self.coords, self.payloads))

                def __iter__(self):
                    return reversed(self.cps)

            fiber = Fiber.fromIterator(reversed_iterator)

        else:
            fiber = self

        # If there is a start_pos, make sure it is in range
        if start_pos is not None:
            assert not fiber.isLazy()

            start_pos = Payload.get(start_pos)
            assert start_pos < len(fiber.coords)

            if interval is not None:
                assert start_pos == 0 \
                    or fiber.coords[start_pos - 1] < interval[0]

        # Build the iterator
        class project_iterator:
            fbr = fiber
            tck = tick
            trans = lambda self, c: trans_fn(c)
            interv = interval
            start = start_pos
            rank = rank_id

            def __init__(self):
                is_collecting = Metrics.isCollecting()
                assert not is_collecting or self.rank is not None

                # Associate the src and dst ranks
                if Metrics.isCollecting():
                    src_rank = self.fbr.getRankAttrs().getId()
                    Metrics.matchRanks(src_rank, self.rank)

            def __iter__(self):
                is_collecting = Metrics.isCollecting()
                traced = False
                if is_collecting:
                    src_rank = self.fbr.getRankAttrs().getId()
                    if tick:
                        Metrics.registerRank(src_rank)

                    label = str(Metrics.getLabel(src_rank))
                    trace = "project_" + label
                    traced = Metrics.isTraced(src_rank, trace)

                    if self.start is None:
                        i = 0
                    else:
                        i = self.start

                    iteration = Metrics.getIter().copy()

                fiter = self.fbr.__iter__(tick=self.tck, start_pos=self.start)
                for j, (old_c, p) in enumerate(fiter):
                    c = self.trans(old_c)
                    if self.interv is not None and c >= self.interv[1]:
                        break

                    if self.interv is None \
                            or (c >= self.interv[0] and c < self.interv[1]):
                        yield c, p

                        if traced:
                            Metrics.addUse(src_rank, old_c, i + j,
                                type_=trace, iteration_num=iteration)
                            iteration = Metrics.getIter().copy()

        if interval:
            min_, max_ = interval

        else:
            start = trans_fn(self.getActive()[0])
            end = trans_fn(Fiber._transCoord(self.getActive()[1], lambda c: c - 1))

            min_ = min(start, end)
            max_ = Fiber._transCoord(max(start, end), lambda c: c + 1)

        result = Fiber.fromIterator(project_iterator, active_range=(min_, max_))
        result._setDefault(self.getDefault())
        if rank_id is not None:
            result.getRankAttrs().setId(rank_id)

        return result


#
# Deprecated coordinate-based methods
#

    def insertOrLookup(self, coord, value=None):
        """.. deprecated::"""

        Fiber._deprecated("Fiber.insertOrLookup() is deprecated use getPayloadRef()")

        if value is None:
            value = self._createDefault()

        payload = Payload.maybe_box(value)

        index = 0
        try:
            index = next(x for x, val in enumerate(self.coords) if val >= coord)
            if self.coords[index] == coord:
                return self.payloads[index]
            self.coords.insert(index, coord)
            self.payloads.insert(index, payload)
            return self.payloads[index]
        except StopIteration:
            self.coords.append(coord)
            self.payloads.append(payload)
            return self.payloads[-1]


    def insert(self, coord, value):
        """.. deprecated::"""

        Fiber._deprecated("Fiber.insert() is deprecated use getPayloadRef()")

        payload = Payload.maybe_box(value)

        try:
            index = next(x for x, val in enumerate(self.coords) if val > coord)
            self.coords.insert(index, coord)
            self.payloads.insert(index, payload)
        except StopIteration:
            self.coords.append(coord)
            self.payloads.append(payload)

        return None


    #
    # Owner rank related methods
    #
    def setOwner(self, owner):
        """Set rank that owns this fiber

        This method allows one to set the **owning rank** of a
        Fiber. This allows support for certain attributes of a Fiber
        that are common to all the fibers in a rank to be accessed
        from the rank. This includes `Fiber.getDefault()`,
        `Fiber.getShape() and `Fiber.getRankId()`.

        Parameters
        ----------

        owner: Rank
            The rank that owns this fiber


        """

        self._owner = owner

    def getOwner(self):
        """Get rank that owns this fiber.

        This method allows one to get the **owning rank** of a
        Fiber.

        Parameters
        ----------
        None

        Returns
        -------
        owner_rank: Rank
            The rank that owns this fiber

        """

        return self._owner

    def setRankAttrs(self, attrs):
        """
        If the fiber does not have an owning rank, it can still have rank attributes

        Parameters
        ----------
        attrs: RankAttrs
            Rank attributes

        Returns
        -------
        None
        """
        assert isinstance(attrs, RankAttrs)
        self._rank_attrs = attrs

    def getRankAttrs(self):
        """
        If the fiber does not have an owning rank, it can still have rank attributes

        Parameters
        ----------
        None

        Returns
        -------
        attrs: RankAttrs
            Rank attributes if set

        """
        if self.getOwner():
            return self.getOwner().getAttrs()

        return self._rank_attrs


    def setActive(self, active_range):
        """
        Set the range of active coordinates for this rank

        Parameters
        ----------
        active_range: Optional[Tuple[int, int]]
            The range of active coordinates; None implies [0, shape)

        Returns
        -------
        None
        """
        if active_range is not None:
            assert isinstance(active_range, tuple)
            assert len(active_range) == 2

        self._active_range = active_range

    def getActive(self):
        """
        Set the range of active coordinates for this rank

        Parameters
        ----------
        None

        Returns
        -------
        active_range: Tuple[int, int]
            The range of active coordinates

        """
        if self._active_range:
            return self._active_range

        shape = self.getRankAttrs().getShape()
        if not shape:
            shape = self.estimateShape(all_ranks=False)

        start = Fiber._transCoord(shape, lambda c: 0)
        return (start, shape)

    #
    # Default payload methods
    #
    def setDefault(self, default):
        """.. deprecated::"""

        Fiber._deprecated("Fiber.setDefault() default values should be set by the owning rank")

        self._setDefault(default)


    def _setDefault(self, default):
        """_setDefault - internal use version"""

        owner = self.getOwner()
        #
        # Try to set default at owning rank, otherwise hold value locally
        #
        if owner is not None:
            owner.setDefault(default)
            return

        self.getRankAttrs().setDefault(default)


    def getDefault(self):
        """Get the default payload for this fiber.

        Ideally the **default** value from a fiber is obtained from the owner rank.

        Parameters
        ----------
        None

        Returns
        -------
        value: value
            A copy of the default payload of fibers in this rank

        Raises
        ------
        None

        """

        #
        # Try to get default from owning rank
        #
        owner = self.getOwner()

        if owner is not None:
            return owner.getDefault()

        #
        # For unowned fibers, try to guess a default value
        #
        # Note: the payload being a Fiber overrides the rank attribute
        #
        if len(self.payloads) > 0 and Payload.contains(self.payloads[0], Fiber):
            return Fiber

        return self.getRankAttrs().getDefault()

    def _createDefault(self, addtorank=True):
        """_createDefault

        Obtain the default payload for a fiber. This method goes one
        step further than getDefault() because if the default payload
        is itself a fiber it creates a Fiber().

        Finally, if the current fiber is part of a a non-leaf rank
        it (optionally) adds the new fiber into the **next** rank.

        TBD: Fold this into an option to getDefault()

        """

        owner = self.getOwner()

        default = self.getDefault()

        a_payload = (self.payloads or [None])[0]
        if isinstance(a_payload, Fiber):
            next_default = a_payload.getDefault()
        else:
            next_default = None

        return Fiber._instantiateDefault(owner, default, next_default, addtorank)


    @staticmethod
    def _instantiateDefault(owner, default, next_default=None, addtorank=False):
        """_instantiateDefault

        Create (recursively for default values that are tuples) an
        instance of a default payload for a fiber. This method goes
        one step further than getDefault() because if the default
        payload is itself (or contains) a fiber it creates a Fiber()
        object.

        Finally, if the newly created fiber is part of a a non-leaf
        rank it (optionally) adds the new fiber into the **next**
        rank.

        Parameters
        ----------

        owner: rank
            The rank that owns the fiber we are creating a payload for

        default: a payload (boxed or unboxed)
            A default value from a fiber

        next_default: a payload (boxed or unboxed)
            If `default` is a Fiber then a default payload for that fiber

        addtorank: Boolean
            If the newly created value is a fiber, then should that fiber
            be added to the its owning rank (owner.next_rank)

        Returns
        -------

        A (boxed) payload

        """
        #
        # Selectively unbox the default
        #
        default = Payload.get(default)

        if isinstance(default, tuple):
            #
            # Recursively create defaults. Note each of the elements of the tuple
            # will be **boxed** as will the final result...
            #
            return Payload(tuple([Fiber._instantiateDefault(owner, e) for e in default]))

        if callable(default):
            #
            # Call the method to create the value
            #
            # Note, currently, this must be a fiber..
            #
            value = default()

            #
            # Conditionaly set the owning rank of the
            # newly created fiber by appending it to the
            # next rank of the tensor.
            #
            # Adding it to the owner.next_rank sets the
            # "default" for the rank, otherwise we set a
            # "default" explcitly.
            #
            # TBD: This is a messy interaction with rank
            #      See Rank.append()
            #
            if Payload.contains(value, Fiber):
                if owner and owner.next_rank is not None:
                    #
                    # The new fiber is nominally part of
                    # "owner.next_rank"
                    #
                    # TBD: Rank.append() sets owner, maybe that should be done here.
                    #
                    if addtorank:
                        #
                        # Actually add it to the rank
                        #
                        owner.next_rank.append(value)
                    else:
                        #
                        # Set the owner, but do not add to rank
                        #
                        value.setOwner(owner.next_rank)
                else:
                    value._setDefault(next_default)
            else:
                assert False, "Unsupported Payload type"
        else:
            assert not isinstance(default, Payload)

            value = default

        return Payload.maybe_box(value)


    #
    # Saved position shortcut related methods
    #

    def setSavedPos(self, position, distance=None):
        """Set the postion for a **shortcut**

        Save the postion in a fiber for use as a future **shortcut**.
        Typically to shorten the duration of some search. The
        (optional) distance is used to maintain statistics on the
        number of elements traversed before arriving at this new
        postion.

        Parameters
        ----------
        postion: integer
            Postion (index) in the fiber to remember

        distance, integer, default=None
            Distance searched to arrive at this postion

        Returns
        -------
        None

        See also
        --------

        `Fiber.getSavedPos()`
        `Fiber.getSavedPosStats()`

        """

        position = Payload.get(position)

        self._saved_pos = position

        #
        # Optionally save distanced moved statistics
        #
        if distance is not None:
            self._saved_count += 1
            self._saved_dist += abs(distance)


    def getSavedPos(self):
        """Set the postion for a **shortcut**

        Get the postion in a fiber for use as a **shortcut**.
        Typically to shorten the duration of some search.

        Parameters
        ----------
        postion: integer
            Postion (index) in the fiber last remembered


        Returns
        -------
        postion: integer


        See also
        --------

        `Fiber.setSavedPos()`
        `Fiber.getSavedPosStats()`

        """

        return self._saved_pos


    def getSavedPosStats(self, clear=True):
        """Get the statistcs assocaited with **shortcuts**

        Get the number of shortcuts used and the distance searched
        using those shortcuts, and optionally clear the statistics


        Parameters
        ----------
        clear: Bool
            Clear the statistics


        Returns
        -------
        stats: tuple
            Tuple of number of **shortcuts** set and total search distance


        See also
        --------

        `Fiber.getSavedPos()`
        `Fiber.setSavedPos()`

        """

        stats = (self._saved_count, self._saved_dist)

        if clear:
            self._clearSavedPosStats()

        return stats


    def _clearSavedPosStats(self):
        """_clearSavedPosStats"""

        self._saved_count = 0
        self._saved_dist = 0

    #
    # Computed attribute acccessors
    #
    def minCoord(self):
        """Return the minimum coordinate that exists in the fiber

        Parameters
        ----------
        None

        Returns
        -------
        min_coordinate: coordinate


        Notes
        -----

        This is only meaningful for coordinates that have an lexographical order.

        """

        assert not self.isLazy()

        # TBD: Should check that the candidate is not an explicit zero

        if len(self.coords) == 0:
            return None

        return min(self.coords)

    def maxCoord(self):
        """Return the maximum coordinate that exists in the fiber

        Parameters
        ----------
        None

        Returns
        -------
        max_coordinate: coordinate


        Notes
        -----

        This is only meaningful for coordinates that have an lexographical order.

        """

        assert not self.isLazy()

        #
        # If _max_coord is set we assume it is correct
        #
        # TBD: _max_coord is not always maintained properly for
        #      some fiber mutations
        #
        if self._max_coord is not None:
            return self._max_coord

        if len(self.coords) == 0:
            return None

        #
        # TBD: Maybe should actually look for largest non-empty coordinate
        #
        if self._ordered:
            return self.coords[-1]
        else:
            return max(self.coords)


    def countValues(self, recursive=True):
        """Count values in the fiber tree

        Count the number of leaf elements in the fibertree
        (recursive=True) or in the current fiber (recursive=False)
        that are not **empty** and have do not have the a payload with
        the fiber's **default** value.

        Parameters
        ----------
        recursive: Bool, default=True
        Find values in leaf nodes (True) or current fiber (False)

        Returns
        -------
        value_count: integer
            Number of non-empty, non-default values.

        Notes
        -----

        If all you actually care about is whether a fiber is empty use
        `Fiber.isEmpty()`

        An explcit zero scalar value will NOT count as a value.

        """

        assert not self.isLazy()

        count = 0
        for p in self.payloads:
            if recursive and Payload.contains(p, Fiber):
                count += Payload.get(p).countValues()
            else:
                count += 1 if not Payload.isEmpty(p, default=self.getDefault()) else 0

        return count

#
# Manage eager vs lazy iteration
#
    def _setIsLazy(self, is_lazy):
        """Set whether or not this fiber is lazily built

        Parameters
        ----------
        is_lazy: bool
            True if this fiber is lazily built

        Returns
        -------
        None

        Notes
        -----
        Mutator should only be used internally

        """
        self._is_lazy = is_lazy

    def isLazy(self):
        """Return true if this fiber is lazily built

        Parameters
        ----------
        None

        Returns
        -------
        is_lazy: bool
            True if this fiber is lazily built

        """
        return self._is_lazy
#
# Position based methods
#
    def __getitem__(self, keys):
        """__getitem__

        For an integer key return a (coordinate, payload) tuple
        containing the contents of a fiber at `position`, i.e., an
        offset in the coordinate and payload arrays. For a slice key
        return a new fiber for the slice

        Parameters
        ----------
        keys: single integer/slicr or tuple of integers/slices
            The positions or slices in an n-D fiber

        Returns
        -------
        tuple or Fiber
            A tuple of a coordinate and payload or a Fiber of the slice

        Raises
        ------

        IndexError
            Index out of range

        TypeError
            Invalid key type

        """

        assert not self.isLazy()

        if not isinstance(keys, tuple):
            # Keys is a single value for 1-D access
            key = keys
            key_cdr = ()
        else:
            # Keys is a tuple for for n-D access
            key = keys[0]
            key_cdr = keys[1:]

        if isinstance(key, int):
            # Handle key as single index

            if key < 0:
                # Handle negative indices
                key += len(self)

            if key < 0 or key >= len(self):
                raise IndexError(f"The index ({key}) is out of range")

            new_payload = self.payloads[key]

            if len(key_cdr):
                # Recurse down the fiber tree
                new_payload = new_payload[key_cdr]

            return CoordPayload(self.coords[key], new_payload)

        if isinstance(key, slice):
            # Key is a slice

            # Get the start, stop, and step from the slice
            slice_range = range(*key.indices(len(self)))

            coords = [self.coords[ii] for ii in slice_range]

            if len(key_cdr):
                # Recurse down the fiber tree for each payload in slice
                payloads = [self.payloads[ii][key_cdr] for ii in slice_range]
            else:
                # Just use each payload in slice
                payloads = [self.payloads[ii] for ii in slice_range]

            return Fiber(coords, payloads)

        raise TypeError("Invalid key type.")


    def __setitem__(self, key, newvalue):
        """__setitem__

        The `newvalue` parameter is either a CoordPayload or an
        arbitrary value to assign to the position "key" in the fiber.
        If `newvalue` is not a CoordPayload or the Coord in the
        CoordPayload is None the current coordinate will be left
        unchanged. The payload will be boxed if appropriate. If the
        payload is None, then the payload will be left unchanged.

        Parameters
        ----------
        key: single integer
            The position in the fiber to be set

        newvalue: a CoordPayload or a payload value
            The coordinate/payload or just payload to assign

        Returns
        -------
        Nothing

        Raises
        ------

        IndexError
            Index out of range

        TypeError
            Invalid key type

        CoordinateError
            Invalid coordinate


        Notes
        ------

        If this fiber does has the "unique" attribute but not the
        "ordered" attribute this method does not check that the new
        coordinate is unique.

        """

        assert not self.isLazy()

        position = key

        #
        # TBD: Get isinstance of CoordPayload to work...
        #
        try:
            coord = newvalue.coord
            payload = newvalue.payload
        except Exception:
            coord = None
            payload = newvalue

        if coord is not None:
            #
            # Check that coordinate order is maintained
            #
            if self._ordered:
                if position > 0 and coord <= self.coords[position - 1]:
                    raise CoordinateError

                if position + 1 < len(self.coords) and coord >= self.coords[position + 1]:
                    raise CoordinateError

            self.coords[position] = coord

        #
        # A payload of None just updates the coordinate
        #
        if payload is not None:
            self.payloads[position] = Payload.maybe_box(payload)


    def __len__(self):
        """__len__

        Find the number of positions in the current fiber. This allows
        one to iterate over the positions in the fiber.

        Parameters
        ----------
        None

        Returns
        -------
        count: int
        Count of positions in the fiber

        Raises
        ------

        None

        Notes
        ------

        This count may contain **empty** (i.e., default)  payloads.

        The semantics of this method for **lazy** fibers is suspect because
        one cannot access laxy fibers by position anyway

        """

        if self.isLazy():
            len_ = 0
            for _ in self.iterOccupancy(tick=False):
                len_ += 1
            return len_

        else:
            return len(self.coords)


    def isEmpty(self):
        """Check if Fiber is empty

        Empty is defined as of zero length, only containing
        **default** values or only containing subfibers that are
        empty.

        Returns
        -------

        empty_p: Bool
            Boolean indicating the fiber was empty


        Notes
        -----

        Need to check for **default** values that are not zero

        """
        assert not self.isLazy()

        return all(map(lambda p: Payload.isEmpty(p, default=self.getDefault()), self.payloads))


    def nonEmpty(self):
        """Create Fiber with only non-empty elements

        Because our fiber representation might have explicit zeros in
        it this method (recursively) creates a new fiber with those
        elements pruned out.

        Returns
        -------

        pruned_fiber: Fiber
            Copy of original fiber with only non-empty elements

        """

        assert not self.isLazy()

        coords = []
        payloads = []

        for c, p in zip(self.coords, self.payloads):
            if not Payload.isEmpty(p, default=self.getDefault()):
                coords.append(c)
                if Payload.contains(p, Fiber):
                    payloads.append(p.nonEmpty())
                else:
                    payloads.append(p)

        return self._newFiber(coords, payloads)

#
# Iterator methods
#
    from .iterators import __iter__
    from .iterators import __reversed__
    from .iterators import iterOccupancy
    from .iterators import iterShape
    from .iterators import iterShapeRef
    from .iterators import iterActive
    from .iterators import iterActiveShape
    from .iterators import iterActiveShapeRef
    from .iterators import iterRange
    from .iterators import iterRangeShape
    from .iterators import iterRangeShapeRef

#
# Dense coiteration methods
#
    @staticmethod
    def coiterShape(*args, **kwargs):
        """Co-iterate in a dense manner over the given fibers

        Note: because we want this to be a static method, we cannot entirely
        move it to the submodule
        """
        return coiterShape(*args, **kwargs)

    @staticmethod
    def coiterShapeRef(*args, **kwargs):
        """Co-iterate in a dense manner over the given fibers using the given
        range

        Note: because we want this to be a static method, we cannot entirely
        move it to the submodule
        """
        return coiterShapeRef(*args, **kwargs)

    @staticmethod
    def coiterActiveShape(*args, **kwargs):
        """Co-iterate in a dense manner over the given fibers, inserting any
        implicit payloads

        Note: because we want this to be a static method, we cannot entirely
        move it to the submodule
        """
        return coiterActiveShape(*args, **kwargs)

    @staticmethod
    def coiterActiveShapeRef(*args, **kwargs):
        """Co-iterate in a dense manner over the given fibers using the given
        range

        Note: because we want this to be a static method, we cannot entirely
        move it to the submodule
        """
        return coiterActiveShapeRef(*args, **kwargs)

    @staticmethod
    def coiterRangeShape(*args, **kwargs):
        """Co-iterate in a dense manner over the given fibers using the given
        range

        Note: because we want this to be a static method, we cannot entirely
        move it to the submodule
        """
        return coiterRangeShape(*args, **kwargs)

    @staticmethod
    def coiterRangeShapeRef(*args, **kwargs):
        """Co-iterate in a dense manner over the given fibers using the given
        range, inserting any implicit payloads

        Note: because we want this to be a static method, we cannot entirely
        move it to the submodule
        """
        return coiterRangeShapeRef(*args, **kwargs)

#
# Core methods
#

    def clear(self):
        """Clear all coordinates/payloads in a fiber

        Returns
        -------
        Nothing

        """

        self.coords.clear()
        self.payloads.clear()

        # No longer lazy
        self._setIsLazy(False)


    def payload(self, coord):
        """.. deprecated::"""

        Fiber._deprecated("Fiber.payload() is deprecated use getPayload()")

        return self.getPayload(coord)


    def append(self, coord, value):
        """Append an element at the end of fiber

        Parameters
        ----------

        coord: scalar
            The coordinate of the element to add to the fiber

        value: payload
            The payload of the elemnt to add to the fiber

        Note
        ----

        For "ordered" fibers, the coordinates in the Fiber must be
        monotonically increasing.

        The "unique" property is not checked for "unordered" fibers.

        The payload will be optionally be **boxed**.

        """

        assert not self.isLazy()

        if self._ordered:
            assert self.maxCoord() is None or self.maxCoord() < coord, \
                   "Fiber coordinates in 'ordered' fibers must be monotonically increasing"

        payload = Payload.maybe_box(value)

        self.coords.append(coord)
        self.payloads.append(payload)


    def extend(self, other):
        """Extend a fiber with another fiber

        Extends the fiber with the contents of another fiber

        Parameters
        ----------
        other: Fiber
            A fiber to extend the original fiber with


        Returns
        -------
        Nothing


        Notes
        ------

        The `other` fiber is not copied, so beware of multiple
        references to the same objects.

        The "unique" property is not checked for "unordered" fibers.

        """

        assert not self.isLazy()

        assert Payload.contains(other, Fiber), \
            "Fibers can only be extended with another fiber"

        if other.isEmpty():
            # Extending with an empty fiber is a nop
            return None

        if self._ordered:
            assert self.maxCoord() is None or self.maxCoord() < other.coords[0], \
                "Fiber coordinates in 'ordered' fibers must be monotonically increasing"

        self.coords.extend(other.coords)
        self.payloads.extend(other.payloads)

        return None


    def updateCoords(self,
                     func,
                     depth=0,
                     rankid=None,
                     new_shape=None,
                     new_rank_id=None):
        """Update (rewrite) the values of the coordinates of a fiber

        Update each coordinate in the the fibers at a depth of `depth`
        below `self` by invoking `func` on it.  Therefore, a depth of
        zero will update the coordinates in the current fiber. Higher
        depths with result in a depth first search down to `depth`
        before traversing the coordinates.

        Parameters
        ----------

        func: function: position, coordinate, payload -> coordinate
            A function that is invoked with each coordinate as its argument

        depth: integer
            The depth in the fiber tree to dive before traversing

        rankid: string, default=None
            The name of a rank, i.e., a rankid, at which to perform
            the update, overrides the `depth` argument.

        new_rankid: string, default=None
            A name of a rank, i.e., a rankid, to give the updated rank

        new_shape: int or tuple, default=None
            A shape specification to give the updated rank

        Returns
        --------
        Nothing

        Raises
        ------

        Nothing


        Notes
        -----

        If the updated coordinates change the type of the shape of the
        rank, then you must change the shape to match. For example, if
        the original coordinates are tuples and they are converted to
        integers, then you should pass in a new shape which will be
        an integer.

        This method checks and that coordinates remain monotonically
        increasing and re-orders to make sure `self.coords` and
        `self.payloads` preserve monotonacity.

        The "unique" property is not checked.

        """

        assert not self.isLazy()

        if len(self.coords) == 0:
            # Nothing to do
            return None

        if rankid is not None:
            depth = self._rankid2depth(rankid)

        if depth > 0:
            # Recurse down to depth...
            for p in self.payloads:
                p.updateCoords(func, depth=depth - 1, new_shape=new_shape)
                return None

        # Update my coordinates

        no_sort_needed = True

        last_coord = None

        for i in range(len(self.coords)):
            new_coord = func(i, self.coords[i], self.payloads[i])
            self.coords[i] = new_coord

            no_sort_needed = no_sort_needed and ((last_coord is None) or (last_coord <= new_coord))
            last_coord = new_coord

        if self._ordered and not no_sort_needed:
            #
            # Resort the coords/payloads
            #
            # self.logger.debug("Fiber.updateCoords() - sort needed")

            zipped_cp = zip(self.coords, self.payloads)
            sorted_cp = sorted(zipped_cp)
            self.coords, self.payloads = [list(tuple) for tuple in zip(*sorted_cp)]

        #
        # Update the fiber's rank_id and/or shape
        #
        if new_rank_id is not None:
            self.getRankAttrs().setId(new_rank_id)

        if new_shape is not None:
            self.getRankAttrs().setShape(new_shape)

        new_shape = self.getRankAttrs().getShape()

        assert isinstance(new_shape, type(self.coords[0])), \
            "Type of shape must match shape of coordinates"

        return None


    def updatePayloads(self, func, depth=0, rankid=None):
        """Update the values of the payloads of a fiber

        Update each payload in the the fibers at a depth of `depth`
        below "self" by invoking "func" on it.  Therefore, a depth of
        zero will update the payloads in the current fiber. Higher
        depths with result in a depth first search down to `depth`
        before traversing the payloads.

        Parameters
        ----------

        func: function: postion, coordinate, payload -> payload
             A function that is invoked with each payload as its argument

        depth: integer
            The depth in the fibertree to dive before traversing

        rankid: string, default=None
            The name of a rank, i.e., a rankid, at which to perform
            the split, overrides the `depth` argument.

        Returns
        --------

        None

        Raises
        ------

        TBD: currently nothing

        """

        assert not self.isLazy()

        if rankid is not None:
            depth = self._rankid2depth(rankid)

        if depth > 0:
            # Recurse down to depth...
            for p in self.payloads:
                p.updatePayloads(func, depth=depth - 1)
        else:
            # Update my payloads
            for i, (c, p) in enumerate(self.iterOccupancy(tick=False)):
                self.payloads[i] = func(i, c, p)

        return None


    def unzip(self):
        """Unzip the payloads of a fiber

        Unzip a fiber whose payloads are a tuple into two fibers each
        with the same coordinates

        Parameters
        ----------

        None

        Returns
        -------

        unziped_fibers: tuple
            A tuple of fibers

        """

        assert not self.isLazy()

        coords_a = list(self.coords)
        coords_b = list(self.coords)

        (payloads_a, payloads_b) = zip(*self.payloads)

        return (self._newFiber(coords_a, payloads_a),
                self._newFiber(coords_b, payloads_b))

#
# Shape-related methods
#

    def getShape(self, all_ranks=True, authoritative=False):
        """Return the shape of a fibertree

        Find the **shape** of the current fiber (`all_ranks`=False) or
        the entire fibertree rooted at the current fiber (`all_ranks`=True)

        Parameters
        ----------

        all_ranks: Bool, default=True

        authoritative: Boolean, default=False
            Control whether to return an estimated (non-authoritative) shape

        Returns
        -------

        shape: integer or list of integers
            The shape of the current fiber or the entire tree

        Note:

        """
        owner = self.getOwner()
        assert owner is not None or not all_ranks or not authoritative

        # If we have an owner, we can just use that value
        if owner is not None:
            shape = owner.getShape(all_ranks=all_ranks, authoritative=authoritative)

        else:
            shape = self.getRankAttrs().getShape()
            if shape and all_ranks:
                # Not authoritative
                rest = []
                for _, p in self:
                    if not isinstance(p, Fiber):
                        continue

                    new_shape = p.getShape(all_ranks=all_ranks, authoritative=authoritative)
                    for i, ns in enumerate(new_shape):
                        # If the new shape has more ranks
                        if i >= len(rest):
                            rest.append(ns)

                        else:
                            rest[i] = max(rest[i], ns)

                shape = [shape] + rest


        if shape is not None or authoritative:
            return shape

        #
        # Backup for cases where there is no  owner or shape was unknown
        #
        shape = self.estimateShape(all_ranks=all_ranks)

        return shape


    def estimateShape(self, all_ranks=True):
        """estimateShape

        Traverse a fiber tree to estimate its shape

        """

        assert not self.isLazy()

        shape = self._calcShape(all_ranks=all_ranks)

        #
        # Since _calcShape() always returns a list we may
        # need to get out first value
        #
        if not all_ranks:
            shape = shape[0]

        return shape


    def _calcShape(self, shape=None, level=0, all_ranks=True):
        """ _calcShape()

        Find the maximum coordinate at each level of the tree

        TBD: Using maximum coordinate isn't really right because
             the original array may have a empty value at its
             maximum coordinate location

        """

        #
        # Start recursion
        #
        if shape is None:
            shape = []

        #
        # Try to determine the maximum coordinate
        #
        max_coord = self.maxCoord()

        #
        # If fiber is empty then shape doesn't change
        #
        if not self.coords:
            if len(shape) < level + 1:
                shape.append(0)

            return shape

        #
        # Update shape for this Fiber at this level
        #
        new_shape = Fiber._transCoord(max_coord, lambda c: c + 1)
        if len(shape) < level + 1:
            shape.append(new_shape)
        else:
            shape[level] = max(shape[level], Fiber._transCoord(max_coord))

        #
        # Recursively process payloads that are Fibers
        #
        if all_ranks and Payload.contains(self.payloads[0], Fiber):
            for p in self.payloads:
                shape = Payload.get(p)._calcShape(shape, level + 1)

        return shape

    @staticmethod
    def _transCoord(coord, trans_fn=lambda c: c):
        """Translate all integers of a coordinate according to the function,
        applying recursively for tuples

        Parameters
        ----------

        coord: Union[int, tuple]
            The coordinate to translate

        trans_fn: int -> int
            A function that translates from a coordinate to a coordinate

        Returns
        -------

        new_coord: Union[int, tuple]
            The coordinate with the function applied to all integers

        """
        assert isinstance(coord, tuple) or isinstance(coord, int) \
            or isinstance(coord, float) or isinstance(coord, Any)

        if isinstance(coord, tuple):
            return tuple(Fiber._transCoord(c, trans_fn) for c in coord)

        elif isinstance(coord, Any):
            return coord

        return trans_fn(coord)

    @staticmethod
    def _nextCoord(coord):
        """Get the very next coordinate, applying recursively for tuples

        Parameters
        ----------

        coord: Union[int, tuple]
            The coordinate to increment

        Returns
        -------

        new_coord: Union[int, tuple]
            The coordinate incremented

        """
        assert isinstance(coord, tuple) or isinstance(coord, int)

        if isinstance(coord, tuple):
            new = list(coord[:-1])
            new.append(Fiber._nextCoord(coord[-1]))
            return tuple(new)

        return coord + 1


#
# Rankid methods
#
    def getRankIds(self, all_ranks=True):
        """Return rankids of a fibertree

        Find the **rank ids** of the current fiber (`all_ranks`=False) or
        the entire fibertree rooted at the current fiber (`all_ranks`=True)

        Parameters
        ----------

        all_ranks: Bool, default=True

        Returns
        -------

        rank_ids: str or list of str
            The rank ids of the current fiber or the entire tree

        """

        owner = self.getOwner()

        if owner is not None:
            return owner.getRankIds(all_ranks=True)

        #
        # Approximate rankids for fiber not in a tensor
        #

        rankids = [f"X.{d}" for d in reversed(range(self.getDepth()))]

        # If a fiber knows its rank name, that is the top rank
        rank_id = self.getRankAttrs().getId()
        if rank_id != "Unknown":
            rankids[0] = rank_id

        return rankids

#
# Dimensionality method
#
    def getDepth(self):
        """Get the depth of the fiber

        Get the depth, i.e., number of dimensions, of the fiber

        Parameters
        ----------
        None

        Returns
        -------
        depth: integer
            The depth of the fibertree

        Raises
        ------
        None

        """

        assert not self.isLazy()

        owner = self.getOwner()

        if owner is not None:
            #
            # In a tensor, so get the number of ranks starting at this fiber
            #
            depth = 0

            while owner is not None:
                depth += 1
                owner = owner.next_rank

            return depth

        #
        # Just have a raw fiber, so count levels
        #
        fiber = self

        depth = 1

        while len(fiber.payloads) > 0 and isinstance(fiber.payloads[0], Fiber):
            depth += 1
            fiber = fiber.payloads[0]

        return depth


#
# Miscelaneous methods
#
    def uncompress(self, shape=None, level=0):
        """Return an uncompressed fibertree (i.e., a nest of lists)

        Recursively create a nest of lists that corresponding to the
        **uncompressed** represention of the current
        fibertree. **Empty** coordinates at a fiber will be
        converted into the **default** value for that fiber.

        Parameters
        ----------

        shape: list of integers, default=None
            Impose a fixed shape on the result


        Returns
        -------
        uncompressed: list of lists

        Notes
        ------

        All elements of the lists are **unboxed**, i.e., never of type
        `Payload`. However, nested elements, e.g., as part of a
        `tuple`, of type `Payload` are not **unboxed**.

        This method only works for "ordered", "unique" fibers.

        """

        assert not self.isLazy()
        assert self._ordered and self._unique

        if shape is None:
            shape = self.getShape(all_ranks=True)

        f = []

        shape_fiber = Fiber(coords=list(range(shape[level])), initial=1)
        for c, (mask, p, _) in self | shape_fiber:

            if (mask == "AB"):
                if Payload.contains(p, Fiber):
                    f.append(Payload.get(p).uncompress(shape, level + 1))
                else:
                    f.append(Payload.get(p))

            if (mask == "B"):
                f.append(self._fillempty(shape, level + 1))

        return f


    def _fillempty(self, shape, level):
        """Recursive fill empty"""

        if level + 1 > len(shape):
            #
            # Find a fiber at the leaf level
            #
            f = self
            while isinstance(f.payloads[0], Fiber):
                f = f.payloads[0]

            #
            # Use the **unboxed** default from the leaf level fiber
            #
            return Payload.get(f.getDefault())

        f = []

        for i in range(shape[level]):
            f.append(self._fillempty(shape, level + 1))

        return f

#
# Arithmetic operations
#

    def __ilshift__(self, other):
        """Fiber assignment

        This operator will make a recursive assignment of all the
        elements of one fiber (`other`) into another fiber (`self`)
        using getPayloadRef(), so subfibers in new fiber are
        properly inserted into their owning rank/tensor

        Note: we use <<= in place of base '=' since we don't want a
        pointer to the existing fiber but an copy of `other` in the
        new fiber.

        Parameters
        ----------

        other: Fiber
            A fiber whose elements will be inserted into `self`

        Notes
        -----

        There is an analogous assignment operator for the `Payload`
        and `CoordPayload` classes, so one can "assign" a new value to
        a "payload" irrespective of whether the "payload" is a
        `Payload`, a `CoordPayload` or a `Fiber`.

        This method is not supported for fibers without the "unique"
        attribute.

        """

        assert not self.isLazy()
        assert Payload.contains(other, Fiber)
        assert self._unique

        if len(self.coords) != 0:
            #
            # Clear out any existing data
            #
            self.coords = []
            self.payloads = []

        self._setDefault(other.getDefault())
        for c, p in other:
            ref = self.getPayloadRef(c)
            ref <<= p

        return self


    def __add__(self, other):
        """Scalar/fiber or fiber/fiber elementwise addition

        This operation does one of two things based on the type of
        `other`. If `other` is a fiber then `other` is added
        element-wise with `self`. Otherwise `other` is treated as a
        scalar and added to each element of `self`. In either case a
        new fiber is created with those sums.

        Parameters
        ----------

        other: scalar | fiber
            The scalar to add to each element of `self`
            or the fiber to add elementwise to `self`

        Returns
        -------

        result_fiber: Fiber
            The fiber after the addition of `other` to `self`


        Examples
        --------

        >>> f = Fiber.fromUncompressed([1, 2, 3, 0, 0, 6])
        >>> f + 2
        Fiber([0, 1, 2, 5], [3, 4, 5, 2, 2, 8])


        Note
        -----

        From the persepctive of modeling activity, this operation has
        implict loops that get exectuted atomically. Therefore, it
        should be used selectively when one is trying to show all the
        activity in a program's flow.

        When doing scalar/fiber addition, empty elements of `self`
        will be treated as zero and the value of `other` will appear
        in the output for those coordinates. When doing fiber/fiber
        addition the result will have the union of the coordinates of
        `self` and `other`.

        """

        assert not self.isLazy()

        coords = []
        payloads = []

        #
        # If `other` is a fiber element-wise add the two fibers
        # Otherwise add `other` to each element of `self`
        #
        if isinstance(other, Fiber):
            for c, (_, self_val, other_val) in self | other:
                coords.append(c)
                payloads.append(self_val + other_val)
        else:
            for c, p in self.iterShape():
                coords.append(c)
                payloads.append(other + p.value)

        return self._newFiber(coords, payloads)


    def __radd__(self, other):
        """ Scalar/fiber addition

        See __add__ for more information.

        Examples
        --------

        >>> f = Fiber.fromUncompressed([1, 2, 3, 0, 0, 6])
        >>> 2 + f
        Fiber([0, 1, 2, 5], [3, 4, 5, 2, 2, 8])

        """

        return self.__add__(other)


    def __iadd__(self, other):
        """Add a scalar or a fiber to a fiber

        This operation does one of two things based on the type of
        `other`. If `other` is a fiber then `other` is added
        elementwise to `self`. Otherwise it is treated as a scalar and
        added to each element of `self`. In either case `self` is
        updated with the sum.

        Parameters
        ----------

        other: scalar | fiber
            The scalar to add to each element of `self`
            or the fiber to add elementwise to `self`

        Returns
        -------

        None


        Examples
        --------

        >>> f = Fiber.fromUncompressed([1, 2, 3, 0, 0, 6])
        >>> f += 2
        >>> f
        Fiber([0, 1, 2, 5], [3, 4, 5, 2, 2, 8])


        Note
        -----

        From the persepctive of modeling activity, this operation has
        implict loops that get exectuted atomically. Therefore, it
        should be used selectively when one is trying to show all the
        activity in a program's flow.

        When doing the addtions, empty elements of `self` will be
        treated as zero and and will be included in the sum (only with
        non-empty coordiantes of `other` if it is a fiber), creating
        new non-empty elements in `self`.

        """

        assert not self.isLazy()

        #
        # If `other` is a fiber add each element of `other` to `self`
        #
        if isinstance(other, Fiber):
            for _, (self_ref, other_val) in self << other:
                self_ref += other_val
            return self

        #
        # Othewise add `other` to each element of `self`
        #
        for c, p in self.iterShapeRef():
            p += other

        return self


    def __mul__(self, other):
        """Scalar/fiber and fiber/fiber elementwise multiplication

        This operation does one of two things based on the type of
        `other`. If `other` is a fiber then `other` is multiplied
        element-wise with `self`. Otherwise `other` is treated as a
        scalar and used to scale each element of `self`. In either
        case a new fiber is created with those products.

        Parameters
        ----------

        other: scalar | Fiber
            The scalar to scale each element of `self` by
            or the fiber to multiply elementwise with `self`.

        Returns
        -------

        result_fiber: Fiber
            A fiber scaled or elementwise multiplied by `other`


        Examples
        --------

        >>> f = Fiber.fromUncompressed([1, 2, 3, 0, 0, 6])
        >>> f * 2
        Fiber([0, 1, 2, 5], [2, 4, 6, 12])

        Notes
        -----

        From the persepctive of modeling activity, this operation has
        implict loops that get exectuted atomically. Therefore, it
        should be used selectively when one is trying to show all the
        activity in a program's flow.

        """

        assert not self.isLazy()

        coords = []
        payloads = []

        if isinstance(other, Fiber):
            for c, (a_val, b_val) in self & other:
                coords.append(c)
                payloads.append(a_val * b_val)
        else:
            for c, p in self:
                coords.append(c)
                payloads.append(other * p.value)

        result = self._newFiber(coords, payloads)
        return result


    def __rmul__(self, other):
        """ Scalar/fiber multiplication

        See __mul__ for more information.

        Examples
        --------

        >>> f = Fiber.fromUncompressed([1, 2, 3, 0, 0, 6])
        >>> 2 * f
        Fiber([0, 1, 2, 5], [2, 4, 6, 12])

        """

        return self.__mul__(other)


    def __imul__(self, other):
        """__imul__

        This operation does one of two things based on the type of
        `other`. If `other` is a fiber then `other` is multiplied
        elementwise by `self`. Otherwise it is treated as a scalar and
        scales each element of `self`. In either case `self` is
        updated with the products.

        Parameters
        ----------

        other: scalar | Fiber
            The scalar to scale each element of `self`
            or the fiber to multiply elementwise to `self`

        Returns
        -------

        None


        Examples
        --------

        >>> f = Fiber.fromUncompressed([1, 2, 3, 0, 0, 6])
        >>> f *= 2
        >>> f
        Fiber([0, 1, 2, 5], [2, 4, 6, 12])

        Notes
        -----

        From the persepctive of modeling activity, this operation has
        implict loops that get exectuted atomically. Therefore, it
        should be used selectively when one is trying to show all the
        activity in a program's flow.

        """
        assert not self.isLazy()

        #
        # If `other` is a fiber, elementwise multiply `other` by `self`
        #
        if isinstance(other, Fiber):
            for c, (self_val, other_val) in self & other:
                #
                # Get a reference to the c coordinate in `self`.  Note
                # that is may be a zero and therefore a hard zero will
                # be included in the final fiber.
                #
                self_ref = self.getPayloadRef(c)
                self_ref <<= self_val * other_val

            return self

        #
        # Othewise multiply `other` to each element of `self`
        #
        for _, p in self:
            p *= other

        return self

#
# Split methods
#
# Note: all these methods return a new fiber
#
    def __truediv__(self, partitions):
        """Split a fiber uniformly in coordinate space into `partitions` partitions

        Parameters
        ----------

        partitions: integer
            The number of partions to split the fiber into


        Returns
        -------

        split_fiber: Fiber
            A fiber split uniformly in coorindate space


        Examples
        --------

        >>> f = Fiber.fromUncompressed([1, 2, 3, 0, 0, 6])
        >>> f / 2
        F[ 0 -> F [ 0 -> 1, 1 -> 2, 2-> 3],
           3 -> F [ 5 -> 6]]


        Notes
        -----

        This method depends on maxCoord() being meaningful

        TBD
        ---

        Is there a reasonable semantic if `partitions` is a fiber
        """
        assert not self.isLazy()

        shape = self.getShape(all_ranks=False)

        assert shape is not None, \
               "Cannot partition a fiber without a maximum coordinate"

        return self.splitUniform((shape+partitions-1)//partitions)


    def __floordiv__(self, partitions):
        """Split a fiber evenly in position space into `partitions` partitions

        Parameters
        ----------

        partitions: integer
            The number of partions to split the fiber into


        Returns
        -------

        split_fiber: Fiber
            A fiber split equally in postion space


        Examples
        --------

        >>> f = Fiber.fromUncompressed([1, 2, 3, 0, 0, 6])
        >>> f / 2
        F[ 0 -> F [ 0 -> 1, 1 -> 2 ],
           2 -> F [ 2 -> 3, 5 -> 6 ]]


        Notes
        -----

        None

        TBD
        ---

        Is there a reasonable semantic if `partitions` is a fiber
        """
        assert not self.isLazy()

        occupancy = len(self.coords)

        return self.splitEqual ((occupancy+partitions-1)//partitions)

    def splitUniform(self, step, relativeCoords=False, depth=0, rankid=None,
            pre_halo=0, post_halo=0):
        """Split a fiber uniformly in coordinate space

        Parameters
        ----------
        step: int
            The `step` between initial coordinates in each split

        relative_coords: bool
            Should the coordinate in the split fibers match the
            original coordinates (`relativeCoords`=False) or always
            start at zero (`relativeCoords`=True)

        depth: integer, default=0
            The depth in the fibertree to perform the split

        rankid: string, default=None
            The name of a rank, i.e., a rankid, at which to perform
            the split, overrides the `depth` argument.

        pre_halo: integer
            The size of the halo before the partition

        post_halo: integer
            The size of the halo after the partition

        Returns
        -------
        split_fiber: Fiber
            A fibertree with one more level corresonding to the
            splits of the original fiber.

        """

        assert not self.isLazy()
        assert isinstance(step, int) and isinstance(pre_halo, int) and isinstance(post_halo, int)
        assert pre_halo >= 0 and post_halo >= 0

        class _SplitterUniform():

            def __init__(self, fiber, step, pre_halo, post_halo, relative):
                self.fiber = fiber
                self.step = step
                self.pre_halo = pre_halo
                self.post_halo = post_halo
                self.relative = relative

            def __iter__(self):
                if len(self.fiber) == 0:
                    return

                assert isinstance(self.fiber.coords[0], int)

                active_start, active_end = self.fiber.getActive()

                upper_coords = []
                lower_coords = []
                lower_payloads = []

                search_start = 0

                for c, p in self.fiber.__iter__(tick=False):
                    # If the coordinate will not be in any partition, skip it
                    if c < active_start - self.pre_halo:
                        continue

                    if c >= active_end + self.post_halo:
                        break

                    # Start at the partition where the coordinate will be in
                    # the post-halo
                    part = (c - self.post_halo) // self.step * self.step
                    # End at the partition where the coordinate will be in the
                    # pre-halo
                    part_end = (c + self.pre_halo) // self.step * self.step + self.step

                    inds = []
                    while part < part_end:
                        # Ensure that this partition is within the active range
                        if part + self.step <= active_start:
                            part += self.step
                            continue
                        elif part >= active_end:
                            break

                        # Add the coordinate to the partition
                        if part in upper_coords[search_start:]:
                            i = upper_coords.index(part)
                        else:
                            i = len(upper_coords)
                            upper_coords.append(part)
                            lower_coords.append([])
                            lower_payloads.append([])

                        inds.append(i)
                        lower_coords[i].append(c)
                        lower_payloads[i].append(p)

                        part += self.step

                    search_start = min(inds)

                for uc, lc, lp in zip(upper_coords, lower_coords, lower_payloads):
                    yield self.build_elem(uc, lc, lp)

            def build_elem(self, part, coords, payloads):
                if relativeCoords:
                    coords = [c - part for c in coords]

                range_start = max(part, self.fiber.getActive()[0])
                range_end = min(part + self.step, self.fiber.getActive()[1])
                active_range = (range_start, range_end)

                return part, coords, payloads, active_range

        if rankid is not None:
            depth = self._rankid2depth(rankid)

        splitter = lambda f: _SplitterUniform(f, step, pre_halo, post_halo, relativeCoords)

        return self._splitGeneric(splitter, depth=depth)


    def splitNonUniform(self, splits, relativeCoords=False, depth=0, rankid=None, pre_halo=0, post_halo=0):
        """Split a fiber non-uniformly in coordinate space

        Parameters
        ----------
        splits: list of integers
            A list of the starting coordinates for each split

        relative_coords: bool
            Should the coordinate in the split fibers match the
            original coordinates (`relativeCoords`=False) or always
            start at zero (`relativeCoords`=True)

        depth: integer, default=0
            The depth in the fibertree to perform the split

        rankid: string, default=None
            The name of a rank, i.e., a rankid, at which to perform
            the split, overrides the `depth` argument.

        pre_halo: integer
            The size of the halo before the partition

        post_halo: integer
            The size of the halo after the partition

        Returns
        -------
        split_fiber: Fiber
            A fibertree with one more level corresonding to the
            splits of the original fiber


        Notes:
        -------
        One does not needs to include a split starting at coordinate zero.

        """
        assert not self.isLazy()
        if isinstance(splits, Fiber):
            splits = splits.getCoords()

        assert all(isinstance(split, int) for split in splits)
        assert isinstance(pre_halo, int) and isinstance(post_halo, int)
        assert pre_halo >= 0 and post_halo >= 0

        class _SplitterNonUniform():

            def __init__(self, fiber, splits, pre_halo, post_halo, relative):
                if Payload.contains(splits, Fiber):
                    splits = splits.coords.copy()
                else:
                    splits = splits.copy()

                self.iter = fiber._splitNonUniform_iter(splits, pre_halo, post_halo, relative)


            def __iter__(self):
                return self.iter


        if rankid is not None:
            depth = self._rankid2depth(rankid)

        splitter = lambda f: _SplitterNonUniform(f, splits, pre_halo, post_halo, relativeCoords)

        return self._splitGeneric(splitter, depth=depth)

    def _splitNonUniform_iter(self, splits, pre_halo, post_halo, relative):
        """Iterator for splitting a fiber non-uniformly in coordinate space

        Parameters
        ----------
        splits: list of integers
            A list of the starting coordinates for each split

        pre_halo: integer
            The size of the halo before the partition

        post_halo: integer
            The size of the halo after the partition
        relative: bool
            Should the coordinate in the split fibers match the
            original coordinates (`relativeCoords`=False) or always
            start at zero (`relativeCoords`=True)

        Returns
        -------
        split_iter: iterator
            An iterator to be used by the split...() methods

        """
        class _SplitterNonUniform_iter():

            def __init__(self, fiber, splits, pre_halo, post_halo, relative):
                self.fiber = fiber
                self.pre_halo = pre_halo
                self.post_halo = post_halo
                self.relative = relative
                self.splits = splits.copy()

            def __iter__(self):
                if len(self.fiber) == 0:
                    return

                assert isinstance(self.fiber.coords[0], int) or \
                    (self.post_halo == 0 and self.pre_halo == 0)

                # If it is after the last coordinate, it is in the last partition
                self.splits.append(Fiber._transCoord(self.fiber.coords[0], lambda c: float("inf")))

                active_start, active_end = self.fiber.getActive()

                lower_coords = [[] for _ in splits]
                lower_payloads = [[] for _ in splits]

                halo_start = self.sub_pre_halo(active_start)
                halo_end = self.add_post_halo(active_end)

                search_start = 0

                for c, p in self.fiber.__iter__(tick=False):
                    if c < halo_start:
                        continue

                    if c >= halo_end:
                        break

                    if c < self.sub_pre_halo(self.splits[search_start]):
                        continue

                    i = search_start
                    inds = []

                    while i < len(splits):
                        if self.splits[i + 1] <= active_start:
                            i += 1
                            continue

                        elif self.splits[i] >= active_end:
                            break

                        elif c >= self.add_post_halo(self.splits[i + 1]):
                            i += 1
                            continue

                        elif c < self.sub_pre_halo(self.splits[i]):
                            break

                        inds.append(i)
                        lower_coords[i].append(c)
                        lower_payloads[i].append(p)

                        i += 1

                    search_start = min(inds)

                for i, (lc, lp) in enumerate(zip(lower_coords, lower_payloads)):
                    if lc:
                        yield self.build_elem(i, lc, lp)

            def add_post_halo(self, coord):
                if self.post_halo != 0:
                    return coord + self.post_halo
                return coord

            def build_elem(self, ind, coords, payloads):
                if relative:
                    coords = [c - self.splits[ind] for c in coords]

                range_start = max(self.splits[ind], self.fiber.getActive()[0])
                range_end = min(self.splits[ind + 1], self.fiber.getActive()[1])
                active_range = (range_start, range_end)

                return self.splits[ind], coords, payloads, active_range

            def sub_pre_halo(self, coord):
                if self.pre_halo != 0:
                    return coord - self.pre_halo
                return coord

        return _SplitterNonUniform_iter(self, splits, pre_halo, post_halo, relative).__iter__()


    def splitEqual(self, step, relativeCoords=False, depth=0, rankid=None, pre_halo=0, post_halo=0):
        """Split a fiber equally in postion space

        Parameters
        ----------
        step: integer
            The `step` in number of elements in each split

        relative_coords: bool
            Should the coordinate in the split fibers match the
            original coordinates (`relativeCoords`=False) or always
            start at zero (`relativeCoords`=True)

        depth: integer, default=0
            The depth in the fibertree to perform the split

        rankid: string, default=None
            The name of a rank, i.e., a rankid, at which to perform
            the split, overrides the `depth` argument.

        pre_halo: integer
            The size of the halo before the partition

        post_halo: integer
            The size of the halo after the partition

        Returns
        -------
        split_fiber: Fiber
            A fibertree with one more level corresponding to the
            splits of the original fiber

        Notes
        -----
        The current implementation performs a splitEqual before the halo in
        order to keep consistent semantics whether or not the halo is 0

        """
        assert not self.isLazy()
        assert isinstance(step, int)
        assert isinstance(pre_halo, int) and isinstance(post_halo, int)
        assert pre_halo >= 0 and post_halo >= 0

        class _SplitterEqual():

            def __init__(self, fiber, step, pre_halo, post_halo, relative):
                splits = []
                for i, (c, _) in enumerate(fiber.iterActive(tick=False)):
                    if i == 0:
                        splits.append(fiber.getActive()[0])

                    elif i % step == 0:
                        splits.append(c)

                self.iter = fiber._splitNonUniform_iter(splits, pre_halo, post_halo, relative)

            def __iter__(self):
                return self.iter

        if rankid is not None:
            depth = self._rankid2depth(rankid)

        splitter = lambda f: _SplitterEqual(f, step, pre_halo, post_halo, relativeCoords)

        return self._splitGeneric(splitter, depth=depth)

    def splitUnEqual(self, sizes, relativeCoords=False, depth=0, rankid=None, pre_halo=0, post_halo=0):
        """Split a fiber unequally in postion space

        Split a fiber by the sizes in `sizes`.

        Parameters
        ----------
        sizes: list of integers
            The `sizes` of the splits in number of elements in each split

        relative_coords: Bool
            Should the coordinate in the split fibers match the
            original coordinates (`relativeCoords`=False) or always
            start at zero (`relativeCoords`=True)

        depth: integer, default=0
            The depth in the fibertree to perform the split

        rankid: string, default=None
            The name of a rank, i.e., a rankid, at which to perform
            the split, overrides the `depth` argument.

        pre_halo: integer
            The size of the halo before the partition

        post_halo: integer
            The size of the halo after the partition

        Returns
        -------
        split_fiber: Fiber
            A fibertree with one more level corresonding to the
            splits of the original fiber

        Notes
        ------
        If there are more coordinates than the sum of the `sizes` all
        remaining coordinates are put into the final split.

        The current implementation performs a splitEqual before the halo in
        order to keep consistent semantics whether or not the halo is 0

        """
        assert not self.isLazy()
        assert all(isinstance(size, numbers.Number) for size in sizes)
        assert isinstance(pre_halo, int) and isinstance(post_halo, int)
        assert pre_halo >= 0 and post_halo >= 0

        class _SplitterUnEqual():

            def __init__(self, fiber, sizes, pre_halo, post_halo, relative):
                splits = []
                j = 0
                base = 0
                for i, (c, _) in enumerate(fiber.iterActive(tick=False)):
                    if j == len(sizes):
                        break

                    if i == 0:
                        splits.append(fiber.getActive()[0])

                    elif i - base == sizes[j]:
                        base = i
                        j += 1
                        splits.append(c)

                self.iter = fiber._splitNonUniform_iter(splits, pre_halo, post_halo, relative)

            def __iter__(self):
                return self.iter

        if rankid is not None:
            depth = self._rankid2depth(rankid)

        splitter = lambda f: _SplitterUnEqual(f, sizes, pre_halo, post_halo, relativeCoords)

        return self._splitGeneric(splitter, depth=depth)


    def _rankid2depth(self, rankid):
        """_rankid2depth

        Finds the depth of a given rankid
        """

        owner = self.getOwner()

        assert owner is not None, "Rankids exist only for fibers in a tensor"

        rankids = owner.getRankIds()

        return rankids.index(rankid)



    def _splitGeneric(self, splitter, depth=0):
        """Generic partitioning function

        Parameters
        ----------

        splitter: Iterator
            An iterator that yields 4 element tuples:
            (partition_coord, coord_list, payload_list, active_range)

        depth: int
            The depth of the rank to actually partition

        Returns
        -------

        fiber: Fiber
            A fiber like self with the top rank split into two according to the
            splitter
        """
        fiber = copy.deepcopy(self)

        if depth == 0:
            return fiber._splitFiber(splitter)

        fiber.updatePayloadsBelow(Fiber._splitFiber, splitter, depth=depth-1)

        # Only clear the owner after the split so that the fiber has the full
        # shape information
        fiber.setOwner(None)
        return fiber

    def _splitFiber(self, splitter):
        """Split a single fiber into two according to the splitter

        Parameters
        ----------

        splitter: Iterator
            An iterator that yields 4 element tuples:
            (partition_coord, coord_list, payload_list, active_range)

        Returns
        -------

        fiber: Fiber
            A fiber like self with the top rank split into two according to the
            splitter

        Notes
        -----

        This method should never be called directly, it should only be invoked
        as a result of a call to Fiber._splitGeneric.

        In light of the above, this method does not copy the fiber (so the
        result may contain references to the payloads of self).

        """
        shape = self.getRankAttrs().getShape()

        upper = Fiber(default=Fiber(),
                      active_range=self.getActive(),
                      shape=shape)

        for part, coords, payloads, active_range in splitter(self):
            lower = Fiber(coords=coords,
                          payloads=payloads,
                          active_range=active_range,
                          default=self.getDefault(),
                          shape=shape)

            upper.coords.append(part)
            upper.payloads.append(lower)

        return upper

#
# Operation methods
#

    def concat(self, other):
        """ concat

        Concatenate two fibers

        TBD: Make sure coordinates are monitonically increasing

        """

        assert not self.isLazy() and not other.isLazy()
        assert Payload.contains(other, Fiber), \
            "Fiber concatenation must involve two fibers"

        #
        # TBD: Set default for Fiber
        #
        return self._newFiber(coords=self.coords + other.coords,
                              payloads=self.payloads + other.payloads)

#
# Iterators
#

    @staticmethod
    def intersection(*args, **kwargs):
        """Intersect a set of fibers.

        Note: because we want this to be a static method, we cannot entirely
        move it to the submodule
        """
        return intersection(*args, **kwargs)

    @staticmethod
    def union(*args, **kwargs):
        """Union a set of fibers.

        Note: because we want this to be a static method, we cannot entirely
        move it to the submodule
        """
        return union(*args, **kwargs)

    from .iterators import __and__
    from .iterators import __or__
    from .iterators import __xor__
    from .iterators import __lshift__
    from .iterators import __sub__
#
# Multilayer methods
#
# Note: all these methods return a new fiber
#
    def swapRanks(self):
        """Swap the (highest) two ranks of the fiber.

        By swapping two ranks this method effects the equivalent of
        merging those two ranks.

        Returns
        -------

        result: Fiber
            The result of swapping the top two ranks of the fiber

        Notes
        -----

        This function relies on flattenRanks() and unflattenRanks().
        FIXME: flattenRanks() could be more general to support all p1 types,
        including tuples.

        Note
        ----

        Currently only supported for "ordered", "unique" fibers.

        """

        assert not self.isLazy()
        assert self._ordered and self._unique

        #
        # Flatten the (highest) two ranks
        #
        # Note: We do not need to deepcopy explicitly, because flattenRanks
        # does the deepcopy for us
        flattened = self.flattenRanks(style="pair")

        # Make sure that the flattened fiber has at least one coordinate
        assert(len(flattened.coords) > 0)

        # Make sure the coord is a >=2-element tuple
        assert(len(flattened.coords[0]) >= 2)

        #
        # Sort on secord coordinate of flattened fiber
        # and create new sorted fiber
        #
        sorted_cp = sorted([(c[::-1], p) for c, p in flattened])

        coords = [c for c, _ in sorted_cp]
        payloads = [p for _, p in sorted_cp]

        flattened_sorted = Fiber(coords, payloads, default=flattened.getDefault())

        #
        # Unflatten to get original coordinates in swapped ranks
        #
        swapped = flattened_sorted.unflattenRanks()

        return swapped


    def flattenRanks(self, depth=0, levels=1, style="tuple"):
        """Flatten two ranks into one - COO-style

        Takes `levels` ranks and **flattens** them into a single
        rank.The coordinates of the combined rank can be created with
        a specified `style`:

        - tuple - flattened tuple of coordinates from all flattend ranks
        - pair - nested tuples of coordinates from all flattend ranks
        - absolute - the coordinate of the lowest rank
        - relative -  the sum of the corrdinate of the flattened ranks
        - linear - linearized tuple, i.e., (up, low) -> up * LOW_SHAPE + low

        Parameters
        ----------

        depth: integer, default=0
            Level of fibertree to split

        levels: integer
            Number of levels to flatten into the top level

        style: One of ['tuple', 'pair', 'absolute', 'relative', 'linear'], default='tuple'


        Returns
        -------

        result: Fiber
            Fiber with `level` ranks flattened into the current rank

        Note
        ----

        Currently only supported for "ordered", "unique" fibers.

        Note: tensor uses keyword `coord_style` instead of `style`

        """
        def merge_fn(ps):
            # Flattening should never merge payloads
            raise ValueError

        return self.mergeRanks(depth=depth, levels=levels, style=style, merge_fn=merge_fn)

    @staticmethod
    def _flattenCoords(c1, c0, style="nested", shape=None):
        """_flattenCoords

        Parameters
        ----------

        c1, c0: int
            Unflattened coordinates

        style: One of ['tuple', 'pair', 'absolute', 'relative', 'linear'], default='tuple'

        shape: Optional[int]
            Shape of the bottom rank being flattened, required for linearizing
            the coordinate

        """

        if style == "tuple":
            #
            # Combine coordinates into a single flat tuple, flattening
            # contents of the individual coordinates that are tuples
            #
            # Convert c1 to tuple, if necessary
            #
            if not isinstance(c1, tuple):
                c1 = (c1, )

            #
            # Convert c0 to tuple, if necessary
            #
            if not isinstance(c0, tuple):
                c0 = (c0,)

            #
            # Concatenate the two coordinates
            #
            c1_c0 = c1 + c0

        elif style == "pair":
            #
            # Create a new coordinate as a two element tuple
            #
            c1_c0 = (c1, c0)

        elif style == "absolute":
            c1_c0 = c0

        elif style == "relative":
            c1_c0 = c1 + c0

        elif style == "linear":
            assert shape is not None
            c1_c0 = c1 * shape + c0

        else:
            assert False, \
                f"Supported coordinate styles are: tuple, pair, absolute, relative, and linear. Got: {style}"

        return c1_c0

    def mergeRanks(self, depth=0, levels=1, style="tuple", merge_fn=None):
        """Merge multiple ranks into one, fibers at the same coordinate are
        merged with union, and payloads at the same coordinate are merged
        with the merge function

        - tuple - flattened tuple of coordinates from all flattend ranks
        - pair - nested tuples of coordinates from all flattend ranks
        - absolute - the coordinate of the lowest rank
        - relative -  the sum of the corrdinate of the flattened ranks
        - linear - linearized tuple, i.e., (up, low) -> up * LOW_SHAPE + low

        Parameters
        ----------

        levels: integer
            Number of levels to flatten into the top level

        style: One of ['tuple', 'pair', 'absolute', 'relative', 'linear'], default='tuple'

        merge_fn: Optional[Callable[[Iterable[Payload]], Payload]]
            Function to merge two elements at the same coordinate
            Default: add the two payloads

        Returns
        -------

        result: Fiber
            Fiber with `level` ranks flattened into the current rank
        """
        assert not self.isLazy()
        assert self._ordered and self._unique

        if merge_fn is None:
            merge_fn = lambda ps: sum(ps)

        # Ensure that we only deepcopy once
        copied = copy.deepcopy(self)

        if depth == 0:
            return copied._mergeRanksHelper(levels=levels, style=style, merge_fn=merge_fn)

        copied.updatePayloadsBelow(Fiber._mergeRanksHelper, depth=depth - 1, levels=levels, style=style, merge_fn=merge_fn)
        copied.setOwner(None)
        return copied

    def _mergeRanksHelper(self, levels=1, style="tuple", merge_fn=None):
        """ Merge the top two ranks of self

        Parameters
        ----------

        levels: integer
            Number of levels to merge into the top level

        style: One of ['tuple', 'pair', 'absolute', 'relative', 'linear'], default='tuple'

        merge_fn: Callable[[Iterable[Payload]], Payload]
            Function to merge two elements at the same coordinate

        Returns
        -------

        result: Fiber
            Fiber with `level` ranks merged into the current rank
        """
        assert merge_fn is not None
        #
        # Merge deeper levels first, if requested
        #
        if levels == 1:
            cur_payloads = self.payloads
        # If the fiber is empty, no need to merge lower levels
        elif not self.coords:
            cur_payloads = self.payloads
        else:
            assert Payload.contains(self.payloads[0], Fiber), \
                "Insuffient levels to merge"

            cur_payloads = []

            for p in self.payloads:
                cur_payloads.append(p._mergeRanksHelper(
                                        levels=levels - 1, style=style, merge_fn=merge_fn))

        coords = []
        payloads = []

        range_start = None
        range_end = None

        default = Payload(0)
        up_shape = self.getShape(all_ranks=False, authoritative=True)
        low_shape = None

        for i, (c1, p1) in enumerate(zip(self.coords, cur_payloads)):
            if not Payload.contains(p1, Fiber):
                raise PayloadError

            if i == 0:
                range_start, range_end = p1.getActive()
            else:
                range_start = min(range_start, p1.getActive()[0])
                range_end = max(range_end, p1.getActive()[1])

            default = p1.getDefault()

            low_shape = p1.getShape(all_ranks=False, authoritative=True)
            for c0, p0 in p1:
                new_coord = self._flattenCoords(c1,
                                                c0,
                                                style=style,
                                                shape=low_shape)

                j = self._coord2pos(new_coord, coords=coords)

                if j < len(coords) and new_coord == coords[j]:
                    payloads[j].append(p0)
                else:
                    coords.insert(j, new_coord)
                    payloads.insert(j, [p0])

        merged_payloads = [Fiber._mergeToFibertree(ps, merge_fn) for ps in payloads]

        # Compute the shape
        shape = None
        if style == "absolute" or style == "relative":
            shape = low_shape
        elif up_shape and low_shape:
            if style == "linear":
                shape = up_shape * low_shape
            elif style == "pair":
                shape = (up_shape, low_shape)
            elif style == "tuple":
                if isinstance(low_shape, tuple):
                    shape = (up_shape,) + low_shape
                else:
                    shape = (up_shape, low_shape)



        # Compute the active range
        active_range = None

        if range_start is None:
            range_start = 0
            range_end = float("inf")

        if style == "tuple" or style == "pair":
            active_range = ((self.getActive()[0], range_start), (self.getActive()[1], range_end))
        elif style == "relative":
            active_range = self.getActive()
        elif style == "absolute":
            active_range = self.getActive()
        elif style == "linear":
            active_range = (0, float("inf"))

        return Fiber(coords, merged_payloads, default=default, active_range=active_range, shape=shape)

    @staticmethod
    def _mergeToFibertree(to_merge, merge_fn):
        """Merge the given list of payloads into a single payload

        Warning: this subroutine does NOT deepcopy anything
        """
        assert len(to_merge) > 0

        if len(to_merge) == 1:
            return to_merge[0]

        # If we are merging together leaves, use the merge function
        if not isinstance(to_merge[0], Fiber):
            return merge_fn(to_merge)

        # Merge fibers together
        coords = []
        payloads = []
        union_fiber = union(*to_merge)
        for c, ps in union_fiber:
            coords.append(c)
            new_merge = Payload.get(ps)[1:]
            payloads.append(Fiber._mergeToFibertree(new_merge, merge_fn))

        result = Fiber(coords, payloads, active_range=union_fiber.getActive())
        return result


    def unflattenRanks(self, levels=1):
        """Unflatten a ranks into two or more ranks

        Takes a single level of a fiber and expands extract out
        `levels` more levels.

        Parameters
        ----------

        levels: integer
           The number of extra levels to create


        Returns
        -------

        result: Fiber
            A fiber with `levels`' levels unflatten from the top level

        Notes
        -----

        This method may not produce the correct result if the original
        fiber was flattened with either the 'relative' or 'absolute'
        styles.

        Note
        ----

        Currently only supported for "ordered", "unique" fibers.

        """

        assert not self.isLazy()
        assert isinstance(self.coords[0], tuple)
        assert self._ordered and self._unique

        #
        # Place to collect cordinates/payloads for new top rank
        #
        coords1 = []
        payloads1 = []

        first = True
        c1_last = sys.maxsize
        coords0 = []
        payloads0 = []

        #
        # Traverse the rank being unflattened in order to collect all
        # the coordinates/payloads to put in the final top (c1) rank
        #
        for cx, p0 in zip(self.coords, self.payloads):
            #
            # Little dance to get the coordinates of the two ranks,
            # which also deals with the case where the coordinates
            # were not nested.
            #
            c1 = cx[0]
            if len(cx) > 2:
                c0 = cx[1:]
            else:
                c0 = cx[1]

            #
            # Check if we finished all the elements of the lower (c0)
            # rank and have moved on to a new coordinate in the higher
            # (c1) rank. If so add the collected c0 coordinates and
            # payloads as a fiber to the c1 rank, and start a new
            # collection of coordinates and fibers.
            #
            if first or (c1 > c1_last):
                if not first:
                    #
                    # Except when starting to work on the first c1
                    # coordinate, add a new coordinate/payload pair
                    # (maybe after a recursive unflattening) to the
                    # new top (c1) rank
                    #
                    coords1.append(c1_last)

                    cur_fiber = Fiber(coords0,
                                      payloads0,
                                      default=self.getDefault())

                    if levels > 1:
                        cur_fiber = cur_fiber.unflattenRanks(levels=levels - 1)

                    payloads1.append(cur_fiber)

                #
                # Start working on a new c1 coordinate (c1_last) and
                # create a place to collect lower rank (c0)
                # coordinates/payloads to form the payload (fiber) of
                # that c1 coordinate.
                #
                first = False
                c1_last = c1
                coords0 = []
                payloads0 = []

            coords0.append(c0)
            payloads0.append(p0)

        #
        # Pick up the last element of the new top rank
        #
        coords1.append(c1_last)

        #
        # Create the new lower (c0) rank
        #

        fiber0 = Fiber(coords0,
                       payloads0,
                       default=self.getDefault())


        #
        # Conditionally recurse
        #
        if levels > 1:
            fiber0 = fiber0.unflattenRanks(levels=levels - 1)

        payloads1.append(fiber0)

        #
        # Create (and return) the new top (c1) rank
        #
        fiber1 = self._newFiber(coords1,
                                payloads1,
                                default=Fiber())

        return fiber1

    def trace(self, trace_type, iteration_num=None):
        """Trace through the subtree specified by a fiber

        Parameters
        ----------

        trace_type: str
            The name of the trace

        iteration_num: Optional[List[int]]
            The iteration to start on (use the default if not specified)

        Returns
        -------

        None

        Note: All ranks in the loop order must already be registered before this
        method is called
        """
        assert Metrics.isCollecting()

        rank = self.getRankAttrs().getId()
        depth = Metrics.getIndex(rank)
        for i, (c, p) in enumerate(self.__iter__(tick=False)):
            Metrics.addUse(rank, c, i, type_=trace_type, iteration_num=iteration_num)

            # Recurse down the tree
            if isinstance(p, Fiber):
                p.trace(trace_type, iteration_num=iteration_num)

                # Only need to reset it if the iteration is being tracked automatically
                # The parent rank is never reset
                p_rank = p.getRankAttrs().getId()
            # Increment the iterator
            if iteration_num is not None:
                iteration_num[depth] += 1
            else:
                Metrics.incIter(rank)

        Metrics.endIter(rank)


#
# Closures to operate on all payloads at a specified depth
#
# Note: all these methods mutate the fibers
#
# TBD: Reimpliment with Guowei's cleaner Python closure/wrapper
#

    def updatePayloadsBelow(self, func, *args, depth=0, **kwargs):
        """updatePayloadsBelow

        Utility function used as a closure on updatePayloads() to
        change all the payloads in fibers at `depth` in the tree by
        applying `func` with parameters *args and **kwargs to the
        payloads.

        """

        update_lambda = lambda i, c, p: func(p, *args, **kwargs)
        return self.updatePayloads(update_lambda, depth=depth)


    splitUniformBelow = partialmethod(updatePayloadsBelow,
                                      splitUniform)

    splitNonUniformBelow = partialmethod(updatePayloadsBelow,
                                         splitNonUniform)

    splitEqualBelow = partialmethod(updatePayloadsBelow,
                                    splitEqual)

    splitUnEqualBelow = partialmethod(updatePayloadsBelow,
                                      splitUnEqual)

    swapRanksBelow = partialmethod(updatePayloadsBelow,
                                   swapRanks)

    flattenRanksBelow = partialmethod(updatePayloadsBelow,
                                      flattenRanks)

    unflattenRanksBelow = partialmethod(updatePayloadsBelow,
                                        unflattenRanks)

#
# Copy operation
#
    def copy(self, preserve_owner=True):
        """Deep copying that allows the owner to not be copied"""
        if not preserve_owner:
            owners = self._detach_owner()

        copied = copy.deepcopy(self)

        if not preserve_owner:
            self._attach_owner(owners)
            copied._attach_attrs(owners)

        return copied


    def __deepcopy__(self, memo):
        """__deepcopy__

        Note: to ensure maintainability, we want to automatically copy
        everything. We use pickling because it is much more performant
        than the default deepcopy

        The no_owner parameter means that the owning rank is not copied
        """
        return pickle.loads(pickle.dumps(self))

    def _detach_owner(self):
        """Detatch the owner from this fiber and its children"""
        owners = {}
        owners[None] = self.getOwner()
        self.setOwner(None)

        for c, p in self.iterOccupancy(tick=False):
            if isinstance(p, Fiber):
                owners[c] = p._detach_owner()

        return owners

    def _attach_attrs(self, owners):
        owner = owners[None]
        if owner is not None:
            self.setRankAttrs(copy.deepcopy(owner.getAttrs()))

        for c, p in self.iterOccupancy(tick=False):
            if isinstance(p, Fiber):
                p._attach_attrs(owners[c])


    def _attach_owner(self, owners):
        """Reattach the owners to this fiber"""
        self.setOwner(owners[None])

        for c, p in self.iterOccupancy(tick=False):
            if isinstance(p, Fiber):
                p._attach_owner(owners[c])


#
#  Comparison operations
#

    def __eq__(self, other):
        """__eq__ - Equality check for Fibers

        Note: explict zeros do not result in inequality
        """
        if not isinstance(other, Fiber):
            return False

        for c, (mask, ps, po) in self | other:
            if mask == "A":
                return False

            if mask == "B":
                return False

            if mask == "AB" and ps != po:
                return False

        return True

#
#  String methods
#
    def print(self, title=None):
        """Print a fiber"""

        if title is not None:
            print("%s" % title)

        print("%s" % self)
        print("")

    def __format__(self, format):
        """__format__

        Format a fiber

        Spec:

        [(<coord spec>,<scalar spec>)][n][*]

        where:
                "n" means add newlines
                "*" means do not truncate with elipsis

        """
        import re

        kwargs = {}

        regex0 = r'(\(.*,.*\))?(n)?(\*)?'
        match0 = re.search(regex0, format)
        group1 = match0.group(1)

        if group1 is not None:
            regex1 = r'\((.*),(.*)\)'
            match1 = re.search(regex1, group1)
            kwargs['coord_fmt'] = match1.group(1)
            kwargs['payload_fmt'] = match1.group(2)

        if match0.group(2) == 'n':
            kwargs['newline'] = True

        if match0.group(3) == '*':
            kwargs['cutoff'] = 10000

        return self.__str__(**kwargs)


    def __str__(self,
                coord_fmt="d",
                payload_fmt="d",
                newline=False,
                cutoff=2,
                indent=0):
        """__str__"""

        if self.isLazy():
            return "(Fiber, fromIterator)"

        def format_coord(coord):
            """Return "coord" properly formatted with "coord_fmt" """

            if not isinstance(coord, tuple):
                return f"{coord:{coord_fmt}}"

            return '(' + ', '.join(format_coord(c) for c in coord) + ')'


        def format_payload(payload):
            """Return "payload" properly formatted with "payload_fmt" """

            try:
                result = f"{payload:{payload_fmt}}"
            except Exception:
                result = f"{payload}"

            return result


        def cond_string(string):
            """Return "string" if newline is True"""

            if newline:
                return string

            return ''

        str = ''

        if self._owner is None:
            str += "F/["
        else:
            str += f"F({self._owner.getId()})/["

        coord_indent = 0
        next_indent = 0
        items = len(self.coords)

        if self.payloads and Payload.contains(self.payloads[0], Fiber):

            for (c, p) in zip(self.coords[0:cutoff], self.payloads[0:cutoff]):
                if coord_indent == 0:
                    coord_indent = indent + len(str)
                    str += f"( {format_coord(c)} -> "
                    if newline:
                        next_indent = indent + len(str)
                else:
                    str += cond_string('\n' + coord_indent * ' ')
                    str += f"( {format_coord(c)} -> "

                str += p.__str__(coord_fmt=coord_fmt,
                                 payload_fmt=payload_fmt,
                                 newline=newline,
                                 cutoff=cutoff,
                                 indent=next_indent)
                str += ')'

            if items > cutoff:
                str += cond_string('\n')
                str += next_indent * ' ' + "..."
                str += cond_string('\n')
                str += next_indent * ' ' + "..."

            return str

        if newline:
            next_indent = indent + len(str)

        for i in range(min(items, cutoff)):
            if coord_indent != 0:
                str += cond_string('\n')

            str += cond_string(coord_indent * ' ')
            str += f"({format_coord(self.coords[i])} -> "
            str += f"{format_payload(self.payloads[i])}) "
            coord_indent = next_indent

        if items > cutoff:
            str += cond_string('\n' + next_indent * ' ')
            str += " ... "
            str += cond_string('\n' + next_indent * ' ')
            str += " ... "

        str += "]"
        return str

    def __repr__(self):
        """__repr__"""

        assert not self.isLazy()

        # TBD: Owner is not properly reflected in representation

        payloads = [Payload.get(r) for r in self.payloads]
        str = f"Fiber({self.coords!r}, {payloads!r}"

        if self._owner:
            str += f", owner={self._owner.getId()}"

        str += ")"

        return str

#
# Yaml input/output methods
#

    @staticmethod
    def parse(yamlfile, default):
        """Parse a yaml file containing a tensor"""

        with open(yamlfile, 'r') as stream:
            try:
                y_file = yaml.safe_load(stream)
            except yaml.YAMLError as exc:
                print(exc)
                exit(1)

        #
        # Make sure key "fiber" exists
        #
        if not isinstance(y_file, dict) or 'fiber' not in y_file:
            print("Yaml is not a fiber")
            exit(1)

        newfiber = Fiber.dict2fiber(y_file)

        return (newfiber.getCoords(), newfiber.getPayloads())



    def dump(self, yamlfile):
        """Dump a tensor to a file in YAML format"""

        fiber_dict = self.fiber2dict()

        with open(yamlfile, 'w') as stream:
            yaml.dump(fiber_dict, stream)

#
# Conversion methods - to/from dictionaries
#

    @staticmethod
    def dict2fiber(y_payload_dict, level=0):
        """Parse a yaml-based tensor payload, creating Fibers as appropriate"""

        if isinstance(y_payload_dict, dict) and 'fiber' in y_payload_dict:
            # Got a fiber, so need to get into the Fiber class

            y_fiber = y_payload_dict['fiber']

            #
            # Error checking
            #
            if not isinstance(y_fiber, dict):
                print("Malformed payload")
                exit(0)

            if 'coords' not in y_fiber:
                print("Malformed fiber")
                exit(0)

            if 'payloads' not in y_fiber:
                print("Malformed fiber")
                exit(0)

            #
            # Process corrdinates and payloads
            #
            f_coords = y_fiber['coords']
            y_f_payloads = y_fiber['payloads']

            f_payloads = []
            for y_f_payload in y_f_payloads:
                f_payloads.append(Fiber.dict2fiber(y_f_payload, level + 1))
            #
            # Turn into a fiber
            #
            subtree = Fiber(coords=f_coords, payloads=f_payloads)
        else:
            # Got scalars, so format is unchanged
            subtree = y_payload_dict

        return subtree



    def fiber2dict(self):
        """Return dictionary with fiber information"""
        assert not self.isLazy()

        f = {'fiber':
             {'coords': self.coords,
              'payloads': [Payload.payload2dict(p) for p in self.payloads]}}

        return f

#
# Utility functions
#
    def _newFiber(self,
                  coords=None,
                  payloads=None,
                  default=None,
                  shape=None,
                  initial=None,
                  max_coord=None,
                  ordered=None,
                  unique=None):
        """Create a new fiber carrying over attributes from `self`

        Note: Input parameters must be kept in sync with `__init__`,
        and certain input parameters that come in as `None` take their
        values from `self`.

        """

        if ordered is None:
            ordered = self._ordered

        if unique is None:
            unique = self._unique

        if default is None:
            default = self.getRankAttrs().getDefault()

        if shape is None:
            shape = self.getRankAttrs().getShape()

        return Fiber(coords=coords,
                     payloads=payloads,
                     default=default,
                     shape=shape,
                     initial=initial,
                     max_coord=max_coord,
                     ordered=ordered,
                     unique=unique)


    def _coord2pos(self, coord, start_pos=None, coords=None):
        """_coord2pos

        Find the position (index) of a coordinate in the fiber or
        where the coordinate should be inserted into the fiber.

        Handles cases where the fiber is "ordered" (using a binary
        search) or "unordered" (using a linear search). Also tries to
        optimize search by using `start_pos` shortcuts.

        If the coordinate is not found return the index where it
        should be inserted, taking into account whether the fiber is
        ordered or unordered.

        Parameters
        ----------

        coord: integer or tuple
            The desired coordinate

        start_pos: integer, default: None
            The starting index (only used for ordered fibers)

        coords: list, default=self.coords
             List of coordinates to search

        Returns
        -------

        index: integer
            The position of the coordinate in the fiber
            or where it can be inserted


        Notes
        -----

        To find out whether the coordinate was found one can use the
        position returned as an argument to the `Fiber._coordExists()`
        method.

        """

        if coords is None:
            coords = self.coords

        if self._ordered:
            #
            # Find coordinate in an ordered fiber
            #
            if start_pos is None:
                #
                # Do a bisection search
                #
                index = bisect.bisect_left(coords, coord)
            else:
                #
                # Search linearly starting at `start_pos`
                # Seach ends when the coordinate is found or passed
                #
                index = len(coords)

                for i in range(start_pos, len(coords)):
                    if coords[i] >= coord:
                        index = i
                        break
        else:
            #
            # Find coordinate in an unordered fiber
            #
            assert start_pos is None, \
                "Unordered fibers do not support `start pos`"

            #
            # Search linearly starting at beginning
            # Seach ends when the coordinate is found
            #
            index = len(coords)

            for i in range(len(coords)):
                if coords[i] == coord:
                    index = i
                    break

        return index

    def _coordExists(self, coord, pos):
        """ _coordExists

        Check if given coordinates exists at the given position

        """

        exists = pos < len(self.coords) and self.coords[pos] == coord

        return exists

    def _checkOrdered(self):
        """ Check that coordinates satisfy the "ordered" attribute """

        if not self._ordered or len(self.coords) == 0:
            return True

        coords = self.coords

        last = coords[0]

        for c in coords[1:]:
            if c <= last:
                assert False, "Illegal non-monotonic coordinate"

            last = c


    def _checkUnique(self):
        """ Check that coordinates satisfy the "unique" attribute """

        if not self._unique:
            return True

        if self._ordered:
            coords = self.coords
        else:
            coords = sorted(self.coords)

        last = None

        for c in coords:
            if c == last:
                assert False, "Illegal repeated coordinate"

            last = c


    @staticmethod
    def _deprecated(message):
        import warnings

        warnings.warn(message, FutureWarning, stacklevel=3)


#
# Pdoc stuff
#
__pdoc__ = {'Fiber.dict2fiber':    False,
            'Fiber.fiber2dict':    False,
            'Fiber.parse':         False,
            'Fiber.__setitem__':   True,
            'Fiber.__getitem__':   True,
            'Fiber.__ilshift__':   True,
            'Fiber.__truediv__':   True,
            'Fiber.__floordiv__':  True,
            'Fiber.__add__':  True,
            'Fiber.__radd__':  True,
            'Fiber.__iadd__':  True,
            'Fiber.__mul__':  True,
            'Fiber.__rmul__':  True,
            'Fiber.__imul__':  True,
            'Fiber.__and__':  True,
            'Fiber.__or__':  True,
            'Fiber.__xor__':  True,
            'Fiber.__lshift__':  True,
            'Fiber.__sub__':  True,
           }


if __name__ == "__main__":

    a = Fiber([2, 4, 6], [3, 5, 7])

    print("Simple print")
    a.print()
    print("----\n\n")
